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

Discussiones Mathematicae Graph Theory (2000)

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

## Access Full Article

top## Abstract

top## How to cite

topTomá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] 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] 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] 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] 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] 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] 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] 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] P. Franklin, The four color problem, Amer. J. Math. 44 (1922) 225-236, doi: 10.2307/2370527. Zbl48.0664.02
- [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] E. Jucovic, Convex polytopes (Veda, Bratislava, 1981). Zbl0468.52007
- [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] 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] P. Wernicke, Über den kartographischen Vierfarbensatz, Math. Ann. 58 (1904) 413-426, doi: 10.1007/BF01444968. Zbl35.0511.01