zbMATH — the first resource for mathematics

The 7-cycle \(C_{7}\) is light in the family of planar graphs with minimum degree 5. (English) Zbl 1115.05022
Summary: A connected graph \(H\) is said to be light in the family of graphs \({\mathcal H}\) there exists a positive integer \(k\) such that each graph \(G\in {\mathcal H}\) that contains an isomorphic copy of \(H\) contains a subgraph \(K\) isomorphic to \(H\) that satisfies the inequality \[ \sum_{v\in V(K)} \deg_G(v)\leq k. \] It is known that an \(r\)-cycle \(C_r\) is light in the family of planar graphs with minimum degree 5 if \(3\leq r\leq 6\), and not light for \(r\geq 11\). We prove that \(C_7\) is also light in this family.

05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
Full Text: DOI
[1] Borodin, O.V., Solution of problems of kotzig and grünbaum concerning the isolation of cycles in planar graphs, Mat. zametki, 46, 9-12, (1989) · Zbl 0694.05027
[2] Fabrici, I.; Hexel, E.; Jendrol’, S.; Walther, H., On vertex-degree restricted paths in polyhedral graphs, Discrete math., 212, 1-2, 61-73, (2000) · Zbl 0946.05047
[3] Fabrici, I.; Jendrol’, S., Subgraphs with restricted degrees of their vertices in planar 3-connected graphs, Graphs combin., 13, 3, 245-250, (1997) · Zbl 0891.05025
[4] Harant, J.; Jendrol’, S.; Tkáč, M., On 3-connected plane graphs without triangular faces, J. combin. theory, ser. B, 77, 1, 150-161, (1999) · Zbl 1027.05030
[5] Jendrol’, S.; Madaras, T., On light subgraphs in plane graphs of minimum degree five, Discuss. math. graph theory, 16, 207-217, (1996) · Zbl 0877.05050
[6] Jendrol’, S.; Madaras, T.; Soták, R.; Tuza, Z., On light cycles in plane triangulations, Discrete math., 197/198, 453-467, (1999) · Zbl 0936.05065
[7] S. Jendrol’, H.-J. Voss, Light subgraphs of graphs embedded in plane and in the projective plane—a survey, Preprint, Institute of Algebra MATH-AL-2-2001, TU Dresden. · Zbl 1259.05045
[8] Kotzig, A., Contribution to the theory of Eulerian polyhedra, Mat. čas. SAV (math. slovaca), 5, 101-113, (1955)
[9] Madaras, T.; Soták, R., The 10-cycle \(C_{10}\) is light in the family of all plane triangulations with minimum degree five, Tatra mountains math. publ., 18, 35-56, (1999) · Zbl 0951.05031
[10] B. Mohar, R. Škrekovski, H.-J. Voss, Light subgraphs in planar graphs of minimum degree 4 and edge degree 9, J. Graph Theor. 44 (2003) 115-131.
[11] R. Soták, private communication.
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.