Note on the weight of paths in plane triangulations of minimum degree 4 and 5

Tomás Madaras

Discussiones Mathematicae Graph Theory (2000)

  • Volume: 20, Issue: 2, page 173-180
  • ISSN: 2083-5892

Abstract

top
The weight of a path in a graph is defined to be the sum of degrees of its vertices in entire graph. It is proved that each plane triangulation of minimum degree 5 contains a path P₅ on 5 vertices of weight at most 29, the bound being precise, and each plane triangulation of minimum degree 4 contains a path P₄ on 4 vertices of weight at most 31.

How to cite

top

Tomás Madaras. "Note on the weight of paths in plane triangulations of minimum degree 4 and 5." Discussiones Mathematicae Graph Theory 20.2 (2000): 173-180. <http://eudml.org/doc/270652>.

@article{TomásMadaras2000,
abstract = {The weight of a path in a graph is defined to be the sum of degrees of its vertices in entire graph. It is proved that each plane triangulation of minimum degree 5 contains a path P₅ on 5 vertices of weight at most 29, the bound being precise, and each plane triangulation of minimum degree 4 contains a path P₄ on 4 vertices of weight at most 31.},
author = {Tomás Madaras},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {weight of path; plane graph; triangulation; weight; path; plane triangulation},
language = {eng},
number = {2},
pages = {173-180},
title = {Note on the weight of paths in plane triangulations of minimum degree 4 and 5},
url = {http://eudml.org/doc/270652},
volume = {20},
year = {2000},
}

TY - JOUR
AU - Tomás Madaras
TI - Note on the weight of paths in plane triangulations of minimum degree 4 and 5
JO - Discussiones Mathematicae Graph Theory
PY - 2000
VL - 20
IS - 2
SP - 173
EP - 180
AB - The weight of a path in a graph is defined to be the sum of degrees of its vertices in entire graph. It is proved that each plane triangulation of minimum degree 5 contains a path P₅ on 5 vertices of weight at most 29, the bound being precise, and each plane triangulation of minimum degree 4 contains a path P₄ on 4 vertices of weight at most 31.
LA - eng
KW - weight of path; plane graph; triangulation; weight; path; plane triangulation
UR - http://eudml.org/doc/270652
ER -

References

top
  1. [1] K. Ando, S. Iwasaki and A. Kaneko, Every 3-connected planar graph has a connected subgraph with small degree sum, Annual Meeting of the Mathematical Society of Japan, 1993 (in Japanese). 
  2. [2] O.V. Borodin, Solution of problems of Kotzig and Grünbaum concerning the isolation of cycles in planar graphs, Mat. Zametki 46 (5) (1989) 9-12. Zbl0694.05027
  3. [3] O.V. Borodin, Minimal vertex degree sum of a 3-path in plane maps, Discuss. Math. Graph Theory 17 (1997) 279-284, doi: 10.7151/dmgt.1055. Zbl0906.05017
  4. [4] O.V. Borodin and D.R. Woodall, Short cycles of low weight in normal plane maps with minimum degree 5, Discuss. Math. Graph Theory 18 (1998) 159-164, doi: 10.7151/dmgt.1071. Zbl0927.05069
  5. [5] I. Fabrici and S. Jendrol', Subgraphs with restricted degrees of their vertices in planar 3-connected graphs, Graphs and Combinatorics 13 (1997) 245-250. Zbl0891.05025
  6. [6] I. Fabrici and S. Jendrol', Subgraphs with restricted degrees of their vertices in planar graphs, Discrete Math. 191 (1998) 83-90, doi: 10.1016/S0012-365X(98)00095-8. Zbl0956.05059
  7. [7] I. Fabrici, E. Hexel, S. Jendrol' and H. Walther, On vertex-degree restricted paths in polyhedral graphs, Discrete Math. 212 (2000) 61-73, doi: 10.1016/S0012-365X(99)00209-5. Zbl0946.05047
  8. [8] P. Franklin, The four color problem, Amer. J. Math. 44 (1922) 225-236, doi: 10.2307/2370527. Zbl48.0664.02
  9. [9] S. Jendrol' and T. Madaras, On light subgraphs in plane graphs of minimum degree five, Discuss. Math. Graph Theory 16 (1996) 207-217, doi: 10.7151/dmgt.1035. Zbl0877.05050
  10. [10] E. Jucovic, Convex polytopes (Veda, Bratislava, 1981). Zbl0468.52007
  11. [11] T. Madaras, Note on weights of paths in polyhedral graphs, Discrete Math. 203 (1999) 267-269, doi: 10.1016/S0012-365X(99)00052-7. Zbl0934.05079
  12. [12] B. Mohar, Light paths in 4-connected graphs in the plane and other surfaces, J. Graph Theory 34 (2000) 170-179, doi: 10.1002/1097-0118(200006)34:2<170::AID-JGT6>3.0.CO;2-P Zbl0946.05034
  13. [13] P. Wernicke, Über den kartographischen Vierfarbensatz, Math. Ann. 58 (1904) 413-426, doi: 10.1007/BF01444968. Zbl35.0511.01

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.