×

zbMATH — the first resource for mathematics

Light subgraphs in planar graphs of minimum degree 4 and edge-degree 9. (English) Zbl 1031.05075
Summary: A graph \(H\) is light in a given class of graphs if there is a constant \(w\) such that every graph of the class which has a subgraph isomorphic to \(H\) also has a subgraph isomorphic to \(H\) whose sum of degrees in \(G\) is \( \leq w\). Let \(\mathcal G\) be the class of simple planar graphs of minimum degree \(\geq 4\) in which no two vertices of degree 4 are adjacent. We denote the minimum such \(w\) by \(w(H)\). It is proved that the cycle \(C_s\) is light if and only if \(3 \leq s \leq 6\), where \(w(C_3) = 21\) and \(w(C_4)\leq 35\). The 4-cycle with one diagonal is not light in \(\mathcal G\), but it is light in the subclass \(\mathcal G^T\) consisting of all triangulations. The star \(K_{1,s}\) is light if and only if \(s\leq 4\). In particular, \(w(K_{1,3}) = 23\). The paths \(P_s\) are light for \(1 \leq s \leq 6\), and heavy for \(s\geq 8\). Moreover, \(w(P_3) = 17\) and \(w(P_4) = 23\).

MSC:
05C38 Paths and cycles
05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ando, Annual Meeting of the Mathematical Society of Japan (1993)
[2] Borodin, Matem Zametki 48 pp 9– (1989)
[3] Borodin, Discuss Math Graph Theory 17 pp 279– (1997) · Zbl 0906.05017 · doi:10.7151/dmgt.1055
[4] Borodin, Discrete Math 186 pp 281– (1998)
[5] Borodin, Discuss Math Graph Theory 18 pp 159– (1998) · Zbl 0927.05069 · doi:10.7151/dmgt.1071
[6] Virus macromolecules and geodesic domes, In: ?A spectrum of mathematics,? Ed., Oxford Univ. Press, 1971, 98 p.
[7] Fabrici, Graphs Combinat 13 pp 245– (1997) · Zbl 0891.05025 · doi:10.1007/BF03353001
[8] Fabrici, Discrete Math 212 pp 61– (2000)
[9] Franklin, Am J Math 44 pp 225– (1922)
[10] In: Eds., Graph Theory 1737-1936, Clarendon Press, Oxford, 1977.
[11] Goldberg, T?hoku Math J 43 pp 104– (1937)
[12] Jendrol, Discuss Math Graph Theory 16 pp 207– (1996) · Zbl 0877.05050 · doi:10.7151/dmgt.1035
[13] Jendrol’, Discrete Math 197-198 pp 453– (1999) · Zbl 0936.05065 · doi:10.1016/S0012-365X(99)90099-7
[14] Lebesgue, J Math Pures Appl 19 pp 27– (1940)
[15] Kotzig, Mat-Fyz ?as Sloven Akad Vied 13 pp 20– (1963)
[16] Madaras, Discus Math Graph Theory 20 pp 173– (2000) · Zbl 0982.05043 · doi:10.7151/dmgt.1117
[17] Madaras, Tatra Mt Math Publ 18 pp 35– (1999)
[18] Mohar, J Graph Theory 34 pp 170– (2000)
[19] Wernicke, Math Ann 58 pp 413– (1904)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.