DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 18(2) (1998) 159-164
DOI: 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(C4) ≤ 25 and w(C5) ≤ 30. These hold because a normal plane map with minimum degree 5 must contain a 4-star with w(K1,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