Download PDF - Note on the weight of paths in plane triangulations of minimum degree 4 and 5All rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

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

Authors 1

Affiliations

  1. Department of Geometry and Algebra, P.J. Šafárik University, Jesenná 5, 041 54 Košice, Slovak Republic

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.

Keywords

ENG
weight of path, plane graph, triangulation

Bibliography

  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.
  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.
  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.
  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.
  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.
  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.
  8. P. Franklin, The four color problem, Amer. J. Math. 44 (1922) 225-236, doi: 10.2307/2370527.
  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.
  10. E. Jucovic, Convex polytopes (Veda, Bratislava, 1981).
  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.
  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
  13. P. Wernicke, Über den kartographischen Vierfarbensatz, Math. Ann. 58 (1904) 413-426, doi: 10.1007/BF01444968.
Discussiones Mathematicae Graph Theory
2000/20/2
Export to PBN, Opens in new tab
Pages:
173-180
Main language of publication
English
Received
1999-04-14
Accepted
2000-08-20
Published
2000

DOI: 10.7151/dmgt.1117

Exact and natural sciences