In this note, precise upper bounds are determined for the minimum degree-sum of the vertices of a 4-cycle and a 5-cycle in a plane triangulation with minimum degree 5: w(C₄) ≤ 25 and w(C₅) ≤ 30. These hold because a normal plane map with minimum degree 5 must contain a 4-star with . These results answer a question posed by Kotzig in 1979 and recent questions of Jendrol’ and Madaras.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1071,
author = {Oleg V. Borodin and Douglas R. Woodall},
title = {Short cycles of low weight in normal plane maps with minimum degree 5},
journal = {Discussiones Mathematicae Graph Theory},
volume = {18},
year = {1998},
pages = {159-164},
zbl = {0927.05069},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1071}
}
Oleg V. Borodin; Douglas R. Woodall. Short cycles of low weight in normal plane maps with minimum degree 5. Discussiones Mathematicae Graph Theory, Tome 18 (1998) pp. 159-164. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1071/
[000] [1] O.V. Borodin, Solution of Kotzig's and Grünbaum's problems on the separability of a cycle in a planar graph, Matem. Zametki 46 (5) (1989) 9-12. (in Russian)
[001] [2] O.V. Borodin and D.R. Woodall, Vertices of degree 5 in plane triangulations (manuscript, 1994).
[002] [3] S. Jendrol' and T. Madaras, On light subgraphs in plane graphs of minimal degree five, Discussiones Math. Graph Theory 16 (1996) 207-217, doi: 10.7151/dmgt.1035. | Zbl 0877.05050
[003] [4] A. Kotzig, From the theory of eulerian polyhedra, Mat. Cas. 13 (1963) 20-34. (in Russian)
[004] [5] A. Kotzig, Extremal polyhedral graphs, Ann. New York Acad. Sci. 319 (1979) 569-570.