Minimal vertex degree sum of a 3-path in plane maps

O.V. Borodin

Discussiones Mathematicae Graph Theory (1997)

  • Volume: 17, Issue: 2, page 279-284
  • ISSN: 2083-5892

Abstract

top
Let wₖ be the minimum degree sum of a path on k vertices in a graph. We prove for normal plane maps that: (1) if w₂ = 6, then w₃ may be arbitrarily big, (2) if w₂ < 6, then either w₃ ≤ 18 or there is a ≤ 15-vertex adjacent to two 3-vertices, and (3) if w₂ < 7, then w₃ ≤ 17.

How to cite

top

O.V. Borodin. "Minimal vertex degree sum of a 3-path in plane maps." Discussiones Mathematicae Graph Theory 17.2 (1997): 279-284. <http://eudml.org/doc/270447>.

@article{O1997,
abstract = {Let wₖ be the minimum degree sum of a path on k vertices in a graph. We prove for normal plane maps that: (1) if w₂ = 6, then w₃ may be arbitrarily big, (2) if w₂ < 6, then either w₃ ≤ 18 or there is a ≤ 15-vertex adjacent to two 3-vertices, and (3) if w₂ < 7, then w₃ ≤ 17.},
author = {O.V. Borodin},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {planar graph; structure; degree; path; weight; plane map; minimum degree sum},
language = {eng},
number = {2},
pages = {279-284},
title = {Minimal vertex degree sum of a 3-path in plane maps},
url = {http://eudml.org/doc/270447},
volume = {17},
year = {1997},
}

TY - JOUR
AU - O.V. Borodin
TI - Minimal vertex degree sum of a 3-path in plane maps
JO - Discussiones Mathematicae Graph Theory
PY - 1997
VL - 17
IS - 2
SP - 279
EP - 284
AB - Let wₖ be the minimum degree sum of a path on k vertices in a graph. We prove for normal plane maps that: (1) if w₂ = 6, then w₃ may be arbitrarily big, (2) if w₂ < 6, then either w₃ ≤ 18 or there is a ≤ 15-vertex adjacent to two 3-vertices, and (3) if w₂ < 7, then w₃ ≤ 17.
LA - eng
KW - planar graph; structure; degree; path; weight; plane map; minimum degree sum
UR - http://eudml.org/doc/270447
ER -

References

top
  1. [1] O.V. Borodin, Solution of Kotzig's and Grünbaum's problems on the separability of a cycle in plane graph, (in Russian), Matem. zametki 48 (6) (1989) 9-12. 
  2. [2] O.V. Borodin, Triangulated 3-polytopes without faces of low weight, submitted. Zbl0956.52010
  3. [3] H. Enomoto and K. Ota, Properties of 3-connected graphs, preprint (April 21, 1994). 
  4. [4] K. Ando, S. Iwasaki and A. Kaneko, Every 3-connected planar graph has a connected subgraph with small degree sum I, II (in Japanese), Annual Meeting of Mathematical Society of Japan, 1993. 
  5. [5] Ph. Franklin, The four colour problem, Amer. J. Math. 44 (1922) 225-236, doi: 10.2307/2370527. Zbl48.0664.02
  6. [6] S. Jendrol', Paths with restricted degrees of their vertices in planar graphs, submitted. Zbl1003.05055
  7. [7] S. Jendrol', A structural property of 3-connected planar graphs, submitted. 
  8. [8] A. Kotzig, Contribution to the theory of Eulerian polyhedra, (in Russian), Mat. Čas. 5 (1955) 101-103. 

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.