Heavy paths, light stars, and big melons
type: Item
instance of: scholarly article
title: Heavy paths, light stars, and big melons
zbMATH Open document ID: 1053.05035
author: Tomáš Madaras
author: Riste Škrekovski
published in: Discrete Mathematics
publication date: 2004-10-01T00:00:00Z
review text: A graph \(H\) is defined to be light in a family \(\mathcal H\) of graphs if there exists a finite number \(w(H,\mathcal H)\) such that each \(G\in\mathcal H\) which contains \(H\) as a subgraph, contains also a subgraph \(K\cong H\) such that the sum of the degrees (in \(G\)) of the vertices of \(K\) (that is, the weight of \(K\) in \(G\)) is at most \(w(H,\mathcal H)\). In this paper the authors study the conditions related to the weight of fixed subgraphs of the plane graphs which can enforce the existence of light graphs in some families of plane graphs. For the families of plane graphs \(\mathcal P(w)\) and triangulations \(\mathcal T(w)\) whose edges are of weight (i.e. the sum of the degrees of endvertices) \(\geq w\) they prove among others the following interesting results: 1. The 4-path \(P_4\) is light in \(\mathcal P(w)\) if and only if \(8\leq w\leq 13\). 2. The 3-cycle \(C_3\) is light in \(\mathcal P(w)\) if and only if \(10\leq w\leq 13\). 3. The 3-cycle \(C_3\) is light in \(\mathcal T(w)\) if and only if \(9\leq w\leq 13\). 4. The 4-cycle \(C_4\) is light in \(\mathcal P(w)\) if and only if \(10\leq w\leq 13\). 5. The star \(K_{1,4}\) is light in \(\mathcal P(w)\) if and only if \(9\leq w\leq 13\). I. Fabrici and the reviewer proved in [Graphs Comb. 13, 245--250 (1997; Zbl 0891.05025)] that the only light graphs in the family of all 3-connected planar graphs are the paths \(P_k\), for every \(k\geq1\).
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 2105618
zbMATH Keywords: planar graph
zbMATH Keywords: light graph
zbMATH Keywords: path
zbMATH Keywords: star
reviewed by: Stanislav Jendroľ
MaRDI profile type: Publication
full work available at URL: j.disc.2003.11.052
OpenAlex ID: W1977377057
cites work: Q3469114
cites work: On the total coloring of planar graphs.
cites work: Minimal vertex degree sum of a 3-path in plane maps
cites work: Short cycles of low weight in normal plane maps with minimum degree 5
cites work: On vertex-degree restricted subgraphs in polyhedral graphs
cites work: On vertex-degree restricted paths in polyhedral graphs
cites work: Subgraphs with restricted degrees of their vertices in planar 3-connected graphs
cites work: On \(3\)-connected plane graphs without triangular faces
cites work: On light subgraphs in plane graphs of minimum degree five
cites work: On light cycles in plane triangulations
cites work: Q4410027
cites work: Q4518403
cites work: Light subgraphs in planar graphs of minimum degree 4 and edge‐degree 9
DOI: 10.1016/J.DISC.2003.11.052
Recommended article: Light subgraphs in planar graphs of minimum degree 4 and edge‐degree 9
Recommended article: Light paths in 4-connected graphs in the plane and other surfaces
Recommended article: On large light graphs in families of polyhedral graphs
Recommended article: On light graphs in 3-connected plane graphs without triangular or quadrangular faces
Recommended article: On light subgraphs in plane graphs of minimum degree five
Recommended article: Light subgraphs of graphs embedded in the plane. A survey
Recommended article: The 7-cycle \(C_{7}\) is light in the family of planar graphs with minimum degree 5
Recommended article: Light graphs in planar graphs of large girth
Recommended article: LIGHT 3-CYCLES IN 1-PLANAR GRAPHS WITH DEGREE RESTRICTIONS
Recommended article: Light subgraphs in graphs with average degree at most four
description: scientific article; zbMATH DE number 2105618