Paths with restricted degrees of their vertices in planar graphs

Stanislav Jendroľ

Czechoslovak Mathematical Journal (1999)

  • Volume: 49, Issue: 3, page 481-490
  • ISSN: 0011-4642

Abstract

top
In this paper it is proved that every 3 -connected planar graph contains a path on 3 vertices each of which is of degree at most 15 and a path on 4 vertices each of which has degree at most 23 . Analogous results are stated for 3 -connected planar graphs of minimum degree 4 and 5 . Moreover, for every pair of integers n ≥ 3 , k ≥ 4 there is a 2 -connected planar graph such that every path on n vertices in it has a vertex of degree k .

How to cite

top

Jendroľ, Stanislav. "Paths with restricted degrees of their vertices in planar graphs." Czechoslovak Mathematical Journal 49.3 (1999): 481-490. <http://eudml.org/doc/30500>.

@article{Jendroľ1999,
abstract = {In this paper it is proved that every $3$-connected planar graph contains a path on $3$ vertices each of which is of degree at most $15$ and a path on $4$ vertices each of which has degree at most $23$. Analogous results are stated for $3$-connected planar graphs of minimum degree $4$ and $5$. Moreover, for every pair of integers $n\ge 3$, $ k\ge 4$ there is a $2$-connected planar graph such that every path on $n$ vertices in it has a vertex of degree $k$.},
author = {Jendroľ, Stanislav},
journal = {Czechoslovak Mathematical Journal},
keywords = {planar graph; path; degree of vertices},
language = {eng},
number = {3},
pages = {481-490},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Paths with restricted degrees of their vertices in planar graphs},
url = {http://eudml.org/doc/30500},
volume = {49},
year = {1999},
}

TY - JOUR
AU - Jendroľ, Stanislav
TI - Paths with restricted degrees of their vertices in planar graphs
JO - Czechoslovak Mathematical Journal
PY - 1999
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 49
IS - 3
SP - 481
EP - 490
AB - In this paper it is proved that every $3$-connected planar graph contains a path on $3$ vertices each of which is of degree at most $15$ and a path on $4$ vertices each of which has degree at most $23$. Analogous results are stated for $3$-connected planar graphs of minimum degree $4$ and $5$. Moreover, for every pair of integers $n\ge 3$, $ k\ge 4$ there is a $2$-connected planar graph such that every path on $n$ vertices in it has a vertex of degree $k$.
LA - eng
KW - planar graph; path; degree of vertices
UR - http://eudml.org/doc/30500
ER -

References

top
  1. On the total coloring of planar graphs, J. Reine Ange. Math. 394 (1989), 180–185. (1989) Zbl0653.05029MR0977440
  2. Computing light edges in planar graphs, In: Topics in Combinatorics and Graph Theory, R. Bodendiek, R. Henn (eds.), Physica-Verlag Heidelbergȳr 1990, pp. 137–144. Zbl0705.05023MR1100031
  3. Precise lower bound for the number of edges of minor weight in planar maps, Math. Slovaca 42 (1992), 129–142. (1992) Zbl0767.05039MR1170097
  4. 10.1007/BF01202794, Combinatorica 13 (1993), 121–125. (1993) Zbl0777.05050MR1221181DOI10.1007/BF01202794
  5. 10.1016/0012-365X(94)E0144-7, Discrete Math. 137 (1995), 45–51. (1995) Zbl0814.05030MR1312443DOI10.1016/0012-365X(94)E0144-7
  6. On light edges and triangles in planar graph of minimum degree five, Math. Nachr. 170 (1994), 19–24. (1994) MR1302363
  7. 10.1007/BF02764716, Israel J. Math. 14 (1973), 390–408. (1973) MR0317982DOI10.1007/BF02764716
  8. Polytopal graphs, In: Studies in Graph Theory, D. R. Fulkerson (eds.), MAA Studies in Mathematics 12, 1975, pp. 201–224. (1975) MR0406868
  9. New views on some old questions of combinatorial geometry, Int. Teorie Combinatorie, Rome, 1973 1 (1976), 451–468. (1976) MR0470861
  10. Analogues for tiling of Kotzig’s theorem on minimal weights of edges, Ann. Discrete Math. 12 (1982), 129–140. (1982) MR0806977
  11. On 3-connected plane graphs without triangular faces, J. Combinatorial Theory B (to appear). (to appear) MR1710537
  12. 10.7151/dmgt.1028, Discussiones Math. Graph Theory 16 (1996), 123–141. (1996) MR1446351DOI10.7151/dmgt.1028
  13. 10.1016/S0167-5060(08)70614-9, Ann. Discrete Math. 51 (1992), 113–116. (1992) MR1206252DOI10.1016/S0167-5060(08)70614-9
  14. On extremal problems concerning weights of edges of graphs, Coll. Math. Soc. J. Bolyai, 60. Sets, Graphs and Numbers, Budapest (Hungary) 1991, North Holland, 1993, pp. 399-410. (1993) MR1218205
  15. Local structures in plane maps and distance colourings, Discrete Math. (to appear). (to appear) MR1830608
  16. 10.1007/BF00183214, Geom. Dedicata 3 (1974), 233–237. (1974) MR0348629DOI10.1007/BF00183214
  17. Contribution to the theory of Eulerian polyhedra, Mat.-Fyz. Časopis Sloven. Akad. Vied 5 (1955), 101–113. (Slovak) (1955) MR0074837
  18. On the theory of Euler polyhedra, Mat.-Fyz. Časopis Sloven. Akad. Vied 13 (1963), 20–31. (Russian) (1963) MR0162176
  19. Extremal polyhedral graphs, Ann. New York Acad. Sci. 319 (1979), 569–570. (1979) 
  20. Quelques conséquences simples de la formule d’Euler, J. Math. Pures Appl. 19 (1940), 19–43. (1940) Zbl0024.28701MR0001903
  21. The Four-Color Problem, Academic Press, New York, 1967. (1967) Zbl0149.21101MR0216979
  22. 10.1007/BF02804013, Israel J. Math. 45 (1983), 281–296. (1983) Zbl0524.05031MR0720304DOI10.1007/BF02804013

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.