Light classes of generalized stars in polyhedral maps on surfaces

Stanislav Jendrol'; Heinz-Jürgen Voss

Discussiones Mathematicae Graph Theory (2004)

  • Volume: 24, Issue: 1, page 85-107
  • ISSN: 2083-5892

Abstract

top
A generalized s-star, s ≥ 1, is a tree with a root Z of degree s; all other vertices have degree ≤ 2. S i denotes a generalized 3-star, all three maximal paths starting in Z have exactly i+1 vertices (including Z). Let be a surface of Euler characteristic χ() ≤ 0, and m():= ⎣(5 + √49-24χ( ))/2⎦. We prove: (1) Let k ≥ 1, d ≥ m() be integers. Each polyhedral map G on with a k-path (on k vertices) contains a k-path of maximum degree ≤ d in G or a generalized s-star T, s ≤ m(), on d + 2- m() vertices with root Z, where Z has degree ≤ k·m() and the maximum degree of T∖Z is ≤ d in G. Similar results are obtained for the plane and for large polyhedral maps on .. (2) Let k and i be integers with k ≥ 3, 1 ≤ i ≤ [k/2]. If a polyhedral map G on with a large enough number of vertices contains a k-path then G contains a k-path or a 3-star S i of maximum degree ≤ 4(k+i) in G. This bound is tight. Similar results hold for plane graphs.

How to cite

top

Stanislav Jendrol', and Heinz-Jürgen Voss. "Light classes of generalized stars in polyhedral maps on surfaces." Discussiones Mathematicae Graph Theory 24.1 (2004): 85-107. <http://eudml.org/doc/270443>.

@article{StanislavJendrol2004,
abstract = {A generalized s-star, s ≥ 1, is a tree with a root Z of degree s; all other vertices have degree ≤ 2. $S_i$ denotes a generalized 3-star, all three maximal paths starting in Z have exactly i+1 vertices (including Z). Let be a surface of Euler characteristic χ() ≤ 0, and m():= ⎣(5 + √49-24χ( ))/2⎦. We prove: (1) Let k ≥ 1, d ≥ m() be integers. Each polyhedral map G on with a k-path (on k vertices) contains a k-path of maximum degree ≤ d in G or a generalized s-star T, s ≤ m(), on d + 2- m() vertices with root Z, where Z has degree ≤ k·m() and the maximum degree of T∖Z is ≤ d in G. Similar results are obtained for the plane and for large polyhedral maps on .. (2) Let k and i be integers with k ≥ 3, 1 ≤ i ≤ [k/2]. If a polyhedral map G on with a large enough number of vertices contains a k-path then G contains a k-path or a 3-star $S_i$ of maximum degree ≤ 4(k+i) in G. This bound is tight. Similar results hold for plane graphs.},
author = {Stanislav Jendrol', Heinz-Jürgen Voss},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {polyhedral maps; embeddings; light subgraphs; path; star; 2-dimensional manifolds; surface; paths; polyhedral map; plane graphs},
language = {eng},
number = {1},
pages = {85-107},
title = {Light classes of generalized stars in polyhedral maps on surfaces},
url = {http://eudml.org/doc/270443},
volume = {24},
year = {2004},
}

TY - JOUR
AU - Stanislav Jendrol'
AU - Heinz-Jürgen Voss
TI - Light classes of generalized stars in polyhedral maps on surfaces
JO - Discussiones Mathematicae Graph Theory
PY - 2004
VL - 24
IS - 1
SP - 85
EP - 107
AB - A generalized s-star, s ≥ 1, is a tree with a root Z of degree s; all other vertices have degree ≤ 2. $S_i$ denotes a generalized 3-star, all three maximal paths starting in Z have exactly i+1 vertices (including Z). Let be a surface of Euler characteristic χ() ≤ 0, and m():= ⎣(5 + √49-24χ( ))/2⎦. We prove: (1) Let k ≥ 1, d ≥ m() be integers. Each polyhedral map G on with a k-path (on k vertices) contains a k-path of maximum degree ≤ d in G or a generalized s-star T, s ≤ m(), on d + 2- m() vertices with root Z, where Z has degree ≤ k·m() and the maximum degree of T∖Z is ≤ d in G. Similar results are obtained for the plane and for large polyhedral maps on .. (2) Let k and i be integers with k ≥ 3, 1 ≤ i ≤ [k/2]. If a polyhedral map G on with a large enough number of vertices contains a k-path then G contains a k-path or a 3-star $S_i$ of maximum degree ≤ 4(k+i) in G. This bound is tight. Similar results hold for plane graphs.
LA - eng
KW - polyhedral maps; embeddings; light subgraphs; path; star; 2-dimensional manifolds; surface; paths; polyhedral map; plane graphs
UR - http://eudml.org/doc/270443
ER -

References

top
  1. [1] 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
  2. [2] 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
  3. [3] B. Grünbaum, New views on some old questions of combinatorial geometry (Int. Theorie Combinatorie, Rome, 1973) 1 (1976) 451-468. 
  4. [4] B. Grünbaum and G.C. Shephard, Analogues for tiling of Kotzig's theorem on minimal weight of edges, Ann. Discrete Math. 12 (1982) 129-140. Zbl0504.05026
  5. [5] J. Harant, S. Jendrol' and M. Tkáč, On 3-connected plane graphs without trianglar faces, J. Combin. Theory (B) 77 (1999) 150-61, doi: 10.1006/jctb.1999.1918. Zbl1027.05030
  6. [6] J. Ivanco, The weight of a graph, Ann. Discrete Math. 51 (1992) 113-116. Zbl0773.05066
  7. [7] S. Jendrol', T. Madaras, R. Soták and Zs. Tuza, On light cycles in plane triangulations, Discrete Math. 197/198 (1999) 453-467. Zbl0936.05065
  8. [8] S. Jendrol' and H.-J. Voss, A local property of polyhedral maps on compact 2-dimensional manifolds, Discrete Math. 212 (2000) 111-120, doi: 10.1016/S0012-365X(99)00329-5. Zbl0946.05029
  9. [9] S. Jendrol' and H.-J. Voss, A local property of large polyhedral maps on compact 2-dimensional manifolds, Graphs and Combinatorics 15 (1999) 303-313, doi: 10.1007/s003730050064. Zbl0933.05044
  10. [10] S. Jendrol' and H.-J. Voss, Light paths with an odd number of vertices in large polyhedral maps, Annals of Combin. 2 (1998) 313-324, doi: 10.1007/BF01608528. Zbl0929.05049
  11. [11] S. Jendrol' and H.-J. Voss, Subgraphs with restricted degrees of their vertices in large polyhedral maps on compact 2-manifolds, European J. Combin. 20 (1999) 821-832, doi: 10.1006/eujc.1999.0341. Zbl0942.05018
  12. [12] S. Jendrol' and H.-J Voss, Light subgraphs of multigraphs on compact 2-dimensional manifolds, Discrete Math. 233 (2001) 329-351, doi: 10.1016/S0012-365X(00)00250-8. Zbl0995.05038
  13. [13] S. Jendrol' and H.-J. Voss, Subgraphs with restricted degrees of their vertices in polyhedral maps on compact 2-manifolds, Annals of Combin. 5 (2001) 211-226, doi: 10.1007/PL00001301. Zbl0990.05035
  14. [14] S. Jendrol' and H.-J. Voss, Light subgraphs of graphs embedded in 2-dimensional manifolds of Euler characteristic ≤ 0 - a survey, in: Paul Erdős and his Mathematics, II (Budapest, 1999) Bolyai Soc. Math. Stud., 11 (János Bolyai Math. Soc., Budapest, 2002) 375-411. Zbl1037.05015
  15. [15] A. Kotzig, Contribution to the theory of Eulerian polyhedra, Math. Cas. SAV (Math. Slovaca) 5 (1955) 111-113. 
  16. [16] 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
  17. [17] B. Mohar, Face-width of embedded graphs, Math. Slovaca 47 (1997) 35-63. Zbl0958.05034
  18. [18] G. Ringel, Map color Theorem (Springer-Verlag Berlin, 1974). 
  19. [19] N. Robertson and R. P. Vitray, Representativity of surface embeddings, in: B. Korte, L. Lovász, H.J. Prömel and A. Schrijver, eds., Paths, Flows and VLSI-Layout (Springer-Verlag, Berlin-New York, 1990) 293-328. Zbl0735.05032
  20. [20] H. Sachs, Einführung in die Theorie der endlichen Graphen, Teil II. (Teubner Leipzig, 1972). Zbl0239.05105
  21. [21] J. Zaks, Extending Kotzig's theorem, Israel J. Math. 45 (1983) 281-296, doi: 10.1007/BF02804013. Zbl0524.05031

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.