×

zbMATH — the first resource for mathematics

Light subgraphs of order at most 3 in large maps of minimum degree 5 on compact 2-manifolds. (English) Zbl 1077.05029
If \(H\) is a subgraph of a graph \(G\), the weight of \(H\) in \(G\) is the sum of the degrees in \(G\) of all vertices of \(H\). Let \(S\) be a closed surface with Euler characteristic \(\chi(S) \leq 0\), and let \({\mathcal P}\) be the class of all graphs of minimum degree at least 5 that can be embedded in \(S\). It is shown that every graph \(G\) in \({\mathcal P}\) with at least \(83| \chi(S)| \) vertices contains a cycle of length 3 whose weight in \(G\) is at most 18. The weight 18 is shown to be best possible. As a corollary, a similar result is obtained for paths of lengths 1 and 2 instead of the 3-cycle. It is also shown that the weight of a path on three vertices can be lowered to 17 if \(G\) has enough vertices of degree more than 6.
This is one of many papers on the same subject. An overview of known results can be found in two surveys written by the same authors [Light subgraphs of graphs embedded in the plane and in the projective plane—a survey, Discrete Math., to appear, and Bolyai Soc. Math. Stud. 11, 375–411 (2002; Zbl 1037.05015)].

MSC:
05C10 Planar graphs; geometric and topological aspects of graph theory
05C99 Graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Borodin, O.V., Solution of problems of kotzig and grünbaum concerning the isolation of cycles in planar graphs, Math. notes, 46, 9-12, (1989), (in Russian) · Zbl 0694.05027
[2] Borodin, O.V.; Woodall, D.R., Short cycles of low weight in normal plane maps with minimum degree five, Discuss. math. graph theorey, 18, 159-164, (1998) · Zbl 0927.05069
[3] Franklin, P., The four color problem, Amer. J. math., 44, 225-236, (1922) · JFM 48.0664.02
[4] 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
[5] 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
[6] Hexel, E., On light graphs in the family of 4-connected planar graphs, Discrete math., 251, 103-107, (2002) · Zbl 0999.05024
[7] Ivančo, J., The weight of a graph, Ann. discrete math., 51, 113-116, (1992) · Zbl 0773.05066
[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.; Tuhársky, M.; Voss, H.-J., A kotzig type theorem for large maps on surfaces, Tatra mt. math. publ., 27, 153-162, (2003) · Zbl 1062.05044
[11] Jendrol’, S.; Voss, H.-J., A local property of polyhedral maps on compact 2-dimensional manifolds, Discrete math., 212, 111-120, (2000) · Zbl 0946.05029
[12] Jendrol’, S.; Voss, H.-J., A local property of large polyhedral maps on compact 2-dimensional manifolds, Graphs combin., 15, 303-313, (1999) · Zbl 0933.05044
[13] Jendrol’, S.; Voss, H.-J., Light paths with an odd number of vertices in large polyhedral maps, Ann. combin., 2, 313-324, (1998) · Zbl 0929.05049
[14] Jendrol’, S.; Voss, H.-J., Light subgraphs of multigraphs on compact 2-dimensional manifolds, Discrete math., 233, 329-351, (2001) · Zbl 0995.05038
[15] Jendrol’, S.; Voss, H.-J., Light paths in large polyhedral maps with prescribed minimum degree, Australas. J. combin., 25, 79-102, (2002) · Zbl 0991.05057
[16] Jendrol’, S.; Voss, H.-J., Light subgraphs of graphs embedded in 2-dimensional manifolds of Euler characteristic ≤ 0—a survey, (), 375-411 · Zbl 1037.05015
[17] S. Jendrol’, H.-J. Voss, Light subgraphs of graphs embedded in the plane and in the projective plane—a survey, Discrete Math. (to appear) · Zbl 1259.05045
[18] Jendrol’, S.; Voss, H.-J., Light subgraphs of order 4 in large maps of minimum degree 5 on compact 2-manifolds, Australas. J. combin., 28, 171-199, (2003) · Zbl 1038.05017
[19] Jendrol’, S.; Voss, H.-J., The cycle C5 is light in large maps of minimum degree 5 on compact 2-manifolds, Bul. acad. stiin te repub. mold., 3, 40, 106-124, (2002) · Zbl 1049.05030
[20] S. Jendrol’, H.-J. Voss, Light and heavy paths in 2-connected plane graphs of given minimum degree (in preparation)
[21] Kotzig, A., Contribution to the theory of Eulerian polyhedra, Math. čas. SAV(math. slovaca), 5, 111-113, (1955)
[22] Kotzig, A., Extremal polyhedral graphs, Ann. New York acad. sci., 319, 569-570, (1979)
[23] Madaras, T.; Soták, R., The 10-cycle C10 is light in the family of all plane triangulations with minimum degree five, Tatra mt. math. publ., 18, 35-56, (1999) · Zbl 0951.05031
[24] Mohar, B., Face-width of embedded graphs, Math. slovaca, 47, 35-63, (1997) · Zbl 0958.05034
[25] Mohar, B., Light paths in 4-connected graphs in the plane and other surfaces, J. graph theory, 34, 170-179, (2000) · Zbl 0946.05034
[26] 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
[27] Ringel, G., Map color theorem, (1974), Springer-Verlag Berlin · Zbl 0287.05102
[28] Robertson, N.; Vitray, R.P., Representativity of surface embeddings, () · Zbl 0735.05032
[29] Sachs, H., Einführung in die theorie der endlichen graphen, Teil II, (1972), Teubner Leipzig
[30] Sanders, D.P., On light edges and triangles in projective planar graphs, J. graph theory, 21, 335-342, (1996) · Zbl 0854.05037
[31] Wernicke, P., Über den kartographischen vierfarbensatz, Math. ann., 58, 413-426, (1904) · JFM 35.0511.01
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.