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

Oleg V. Borodin; Douglas R. Woodall

Discussiones Mathematicae Graph Theory (1998)

  • Volume: 18, Issue: 2, page 159-164
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Oleg V. Borodin, and Douglas R. Woodall. "Short cycles of low weight in normal plane maps with minimum degree 5." Discussiones Mathematicae Graph Theory 18.2 (1998): 159-164. <http://eudml.org/doc/270522>.

@article{OlegV1998,
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.},
author = {Oleg V. Borodin, Douglas R. Woodall},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {planar graphs; plane triangulation; light subgraphs; weight},
language = {eng},
number = {2},
pages = {159-164},
title = {Short cycles of low weight in normal plane maps with minimum degree 5},
url = {http://eudml.org/doc/270522},
volume = {18},
year = {1998},
}

TY - JOUR
AU - Oleg V. Borodin
AU - Douglas R. Woodall
TI - Short cycles of low weight in normal plane maps with minimum degree 5
JO - Discussiones Mathematicae Graph Theory
PY - 1998
VL - 18
IS - 2
SP - 159
EP - 164
AB - 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.
LA - eng
KW - planar graphs; plane triangulation; light subgraphs; weight
UR - http://eudml.org/doc/270522
ER -

References

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

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.