zbMATH — the first resource for mathematics

Lightness, heaviness and gravity. (English) Zbl 1111.05027
Summary: The gravity \(g(H,\mathcal H)\) of a graph \(H\) in the family of graphs \(\mathcal H\) is the greatest integer \(n\) with the property that for every integer \(m\), there exists a supergraph \(G\in \mathcal H\) of \(H\) such that each subgraph of \(G\) which is isomorphic to \(H\) contains at least \(n\) vertices of degree \(\geqslant m\) in \(G\). We study the basic properties of the gravity function for various families of plane graphs. We also introduce and study the almost-light graphs and the absolutely heavy graphs. The paper concludes with few open problems.

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] Borodin, O.V., Minimal vertex degree sum of a 3-path in plane maps, Discuss. math. graph theory, 17, 279-284, (1997) · Zbl 0906.05017
[3] Fabrici, I.; Jendrol’, S., Subgraphs with restricted degrees of their vertices in planar 3-connected graphs, Graphs combin., 13, 245-250, (1997) · Zbl 0891.05025
[4] Jendrol’, S., A structural property of convex 3-polytopes, Geom. dedicata, 68, 91-99, (1997) · Zbl 0893.52007
[5] Jendrol’, S., Paths with restricted degrees of their vertices in planar graphs, Czechoslovak math. J., 49, (1999) · Zbl 1003.05055
[6] 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
[7] 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
[8] S. Jendrol’, H.-J. Voss, Light subgraphs of graphs embedded in plane and projective plane—a survey—, Preprint Inst. of Algebra MATH-AL-2-2001, TU Dresden. · Zbl 1259.05045
[9] Kotzig, A., Contribution to the theory of Eulerian polyhedra, Mat. čas. SAV (math. slovaca), 5, 101-113, (1955)
[10] Lebesgue, H., Quelques consequences simples de la formule d’euler, J. math. pures appl., 19, 19-43, (1940) · JFM 66.0736.03
[11] T. Madaras, R. Škrekovski, Heavy paths, light stars and big melons, Discrete Math. 286 (2004) 115-131. · Zbl 1053.05035
[12] Mohar, B.; Škrekovski, R.; Voss, H.-J., Light subgraphs in planar graphs of minimum degree 4 and edge degree 9, J. graph theory, 44, 261-295, (2003) · Zbl 1031.05075
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.