ArticleOriginal scientific text

Title

Short cycles of low weight in normal plane maps with minimum degree 5

Authors 1, 2

Affiliations

  1. Novosibirsk State University, Siberian Branch, Russian Academy of Sciences, Novosibirsk, 630090, Russia
  2. 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(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

Bibliography

  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.
Pages:
159-164
Main language of publication
English
Received
1997-08-29
Accepted
1998-03-25
Published
1998
Exact and natural sciences