ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2018: 0.763
Rejection Rate (2017-2018): c. 84%
Mathematicae Graph Theory 18(2) (1998) 159-164DOI: 10.7151/dmgt.1071
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
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.
Received 29 August 1997
Revised 25 March 1998