×

zbMATH — the first resource for mathematics

Light graphs in families of polyhedral graphs with prescribed minimum degree, face size, edge and dual edge weight. (English) Zbl 1222.05217
Summary: A graph \(H\) is defined to be light in a family \(\mathcal H\) of graphs if there exists a finite number \(\varphi(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 \(\varDelta _G(K)\leq \varphi(H,\mathcal H)\). We study light graphs in families of polyhedral graphs with prescribed minimum vertex degree \(\delta \), minimum face degree \(\rho \), minimum edge weight \(w\) and dual edge weight \(w^{*}\). For those families, we show that there exists a variety of small light cycles; on the other hand, we also present particular constructions showing that, for certain families, the spectrum of short cycles contains irregularly scattered cycles that are not light.

MSC:
05C75 Structural characterization of families of graphs
05C38 Paths and cycles
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Borodin, O.V., Joint generalization of the Lebesgue and kotzig theorems on combinatorics of plane maps, Diskret. mat., 3, 4, 24-27, (1991), (in Russian) · Zbl 0742.05034
[2] Borodin, O.V.; Woodall, D., Short cycles of low weight in normal plane maps with minimum degree 5, Discuss. math. graph theory, 16, 159-164, (1998) · Zbl 0927.05069
[3] 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
[4] 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
[5] Ferencová, B.; Madaras, T., On the structure of polyhedral graphs with prescribed edge and dual edge weight, Acta univ. M. belii, 12, 13-18, (2005) · Zbl 1103.05026
[6] R. Hajduk, R. Soták, On large light graphs in families of polyhedral graphs, Discrete Math., in press (doi:10.1016/j.disc.2009.03.008) · Zbl 1216.05123
[7] 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
[8] 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
[9] 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
[10] Jendrol’, S.; Owens, P., On light graphs in 3-connected plane graphs without triangular or quadrangular faces, Graphs combin., 17, 4, 659-680, (2001) · Zbl 0988.05031
[11] S. Jendrol’, H.-J. Voss, Light subgraphs of graphs embedded in the plane and in the projective plane — A survey (submitted for publication) · Zbl 1259.05045
[12] P. Hudák, Š. Kocel’ová, T. Madaras, On the structure of plane graphs extremal according to Kotzig theorem, Preprint, Inst. of Algebra MATH-AL-2-2001, TU Dresden
[13] Kotzig, A., Contribution to the theory of Eulerian polyhedra, Mat. čas. SAV (math. slovaca), 5, 101-113, (1955)
[14] Lebesgue, H., Quelques consequences simples de la formule d’euler, J. math. pures appl., 19, 19-43, (1940) · JFM 66.0736.03
[15] 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
[16] Madaras, T.; Škrekovski, R., Heavy paths, light stars and big melons, Discrete math., 286, 115-131, (2004) · Zbl 1053.05035
[17] Madaras, T.; Škrekovski, R., Lightness, heaviness and gravity, Discrete math., 307, 939-951, (2007) · Zbl 1111.05027
[18] Madaras, T.; Škrekovski, R.; Voss, H.-J., The 7-cycle \(C_7\) is light in the family of all plane graphs with minimum degree 5, Discrete math., 307, 1430-1435, (2007) · Zbl 1115.05022
[19] 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
[20] Robertson, N.; Sanders, D.P.; Seymour, P.D.; Thomas, R., The four-colour theorem, J. combin. theory ser. B, 70, 2-44, (1999) · Zbl 0883.05056
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.