# 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

## Access Full Article

top## Abstract

top## How to cite

topStanislav 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] 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] 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] B. Grünbaum, New views on some old questions of combinatorial geometry (Int. Theorie Combinatorie, Rome, 1973) 1 (1976) 451-468.
- [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] 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] J. Ivanco, The weight of a graph, Ann. Discrete Math. 51 (1992) 113-116. Zbl0773.05066
- [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] 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] 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] 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] 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] 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] 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] 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] A. Kotzig, Contribution to the theory of Eulerian polyhedra, Math. Cas. SAV (Math. Slovaca) 5 (1955) 111-113.
- [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] B. Mohar, Face-width of embedded graphs, Math. Slovaca 47 (1997) 35-63. Zbl0958.05034
- [18] G. Ringel, Map color Theorem (Springer-Verlag Berlin, 1974).
- [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] H. Sachs, Einführung in die Theorie der endlichen Graphen, Teil II. (Teubner Leipzig, 1972). Zbl0239.05105
- [21] J. Zaks, Extending Kotzig's theorem, Israel J. Math. 45 (1983) 281-296, doi: 10.1007/BF02804013. Zbl0524.05031

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.