zbMATH — the first resource for mathematics

On large light graphs in families of polyhedral graphs. (English) Zbl 1216.05123
Summary: A graph \(H\) is said to be light in a family \(\mathcal H\) of graphs if each graph \(G \in \mathcal H\) containing a subgraph isomorphic to \(H\) contains also an isomorphic copy of \(H\) such that each its vertex has the degree (in \(G\)) bounded above by a finite number \(\varphi (H, \mathcal H)\) depending only on \(H\) and \(\mathcal H\). We prove that in the family of all 3-connected plane graphs of minimum degree 5 (or minimum face size 5, respectively), the paths with certain small graphs attached to one of its ends are light.

05C75 Structural characterization of families of graphs
Full Text: DOI
[1] Fabrici, I.; Hexel, E.; Jendrol’, S.; Walther, H., On vertex – degree restricted paths in polyhedral graphs, Discrete math., 212, 61-73, (2000) · Zbl 0946.05047
[2] 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
[3] Harant, J.; Jendrol’, S.; Tkáč, M., On 3-connected plane graphs without triangular faces, J. combin. theory ser. B, 77, 150-161, (1999) · Zbl 1027.05030
[4] 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
[5] Jendrol’, S.; Owens, P., On light subgraphs in 3-connected plane graphs without triangular or quadrangular faces, Graphs combin., 17, 659-680, (2001) · Zbl 0988.05031
[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 the plane and in the projective plane — A survey, Discrete Math. (submitted for publication) · 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., On the structure of plane graphs with minimum face size 5, Discuss. math. graph theory, 24, 3, 403-411, (2004) · Zbl 1063.05038
[10] Madaras, T.; Soták, R., The 10-cycle \(C_{10}\) is light in the family of all plane triangulations with minimum degree five, Tatra mt. math. publ., 18, 35-56, (1999) · Zbl 0951.05031
[11] Madaras, T.; Škrekovski, R., Heavy paths, light stars and big melons, Discrete math., 286, 115-131, (2004) · 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.