PDF

Discussiones Mathematicae Graph Theory 18(2) (1998) 159-164
DOI: https://doi.org/10.7151/dmgt.1071

SHORT CYCLES OF LOW WEIGHT IN NORMAL PLANE MAPS WITH MINIMUM DEGREE 5

Oleg V. Borodin Novosibirsk State University Siberian Branch, Russian Academy of Sciences Novosibirsk, 630090, Russia

Douglas R. Woodall Department of Mathematics, University of Nottingham Nottingham, NG7 2RD, England

Abstract

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 w(K_1,4) ≤ 30. These results answer a question posed by Kotzig in 1979 and recent questions of Jendrol' and Madaras.

Keywords: planar graphs, plane triangulation.

1991 Mathematics Subject Classification: 05C75, 05C10, 05C38.

References

[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)
[2]	O.V. Borodin and D.R. Woodall, Vertices of degree 5 in plane triangulations (manuscript, 1994).
[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.
[4]	A. Kotzig, From the theory of eulerian polyhedra, Mat. Cas. 13 (1963) 20-34. (in Russian)
[5]	A. Kotzig, Extremal polyhedral graphs, Ann. New York Acad. Sci. 319 (1979) 569-570.

Received 29 August 1997
Revised 25 March 1998