# Paths of low weight in planar graphs

Igor Fabrici; Jochen Harant; Stanislav Jendrol'

Discussiones Mathematicae Graph Theory (2008)

- Volume: 28, Issue: 1, page 121-135
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topIgor Fabrici, Jochen Harant, and Stanislav Jendrol'. "Paths of low weight in planar graphs." Discussiones Mathematicae Graph Theory 28.1 (2008): 121-135. <http://eudml.org/doc/270221>.

@article{IgorFabrici2008,

abstract = {The existence of paths of low degree sum of their vertices in planar graphs is investigated. The main results of the paper are:
1. Every 3-connected simple planar graph G that contains a k-path, a path on k vertices, also contains a k-path P such that for its weight (the sum of degrees of its vertices) in G it holds
$w_G(P): = ∑_\{u∈ V(P)\} deg_G(u) ≤ (3/2)k² + (k)$
2. Every plane triangulation T that contains a k-path also contains a k-path P such that for its weight in T it holds
$w_T(P): = ∑_\{u∈ V(P)\} deg_T(u) ≤ k² +13 k$
3. Let G be a 3-connected simple planar graph of circumference c(G). If c(G) ≥ σ| V(G)| for some constant σ > 0 then for any k, 1 ≤ k ≤ c(G), G contains a k-path P such that
$w_G(P) = ∑_\{u∈ V(P)\} deg_G(u) ≤ (3/σ + 3)k$.},

author = {Igor Fabrici, Jochen Harant, Stanislav Jendrol'},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {planar graphs; polytopal graphs; paths; weight of an edge; weight of a path; weight of path},

language = {eng},

number = {1},

pages = {121-135},

title = {Paths of low weight in planar graphs},

url = {http://eudml.org/doc/270221},

volume = {28},

year = {2008},

}

TY - JOUR

AU - Igor Fabrici

AU - Jochen Harant

AU - Stanislav Jendrol'

TI - Paths of low weight in planar graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2008

VL - 28

IS - 1

SP - 121

EP - 135

AB - The existence of paths of low degree sum of their vertices in planar graphs is investigated. The main results of the paper are:
1. Every 3-connected simple planar graph G that contains a k-path, a path on k vertices, also contains a k-path P such that for its weight (the sum of degrees of its vertices) in G it holds
$w_G(P): = ∑_{u∈ V(P)} deg_G(u) ≤ (3/2)k² + (k)$
2. Every plane triangulation T that contains a k-path also contains a k-path P such that for its weight in T it holds
$w_T(P): = ∑_{u∈ V(P)} deg_T(u) ≤ k² +13 k$
3. Let G be a 3-connected simple planar graph of circumference c(G). If c(G) ≥ σ| V(G)| for some constant σ > 0 then for any k, 1 ≤ k ≤ c(G), G contains a k-path P such that
$w_G(P) = ∑_{u∈ V(P)} deg_G(u) ≤ (3/σ + 3)k$.

LA - eng

KW - planar graphs; polytopal graphs; paths; weight of an edge; weight of a path; weight of path

UR - http://eudml.org/doc/270221

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 Mathematical Society of Japan, 1993, Japanese.
- [2] G. Chen and X. Yu, Long cycles in 3-connected graphs, J. Combin. Theory (B) 86 (2002) 80-99, doi: 10.1006/jctb.2002.2113. Zbl1025.05036
- [3] E. Etourneau, Existence and connectivity of planar having 12 vertices of degree 5 and, n-12 vertices of degree 6, Colloq. Math. Soc. János Bolyai 10 (1975) 645-655. Zbl0307.05107
- [4] H. Enomoto and K. Ota, Connected subgraphs with small degree sum in 3-connected planar graphs, J. Graph Theory 30 (1999) 191-203, doi: 10.1002/(SICI)1097-0118(199903)30:3<191::AID-JGT4>3.0.CO;2-X Zbl0916.05020
- [5] I. Fabrici and S. Jendrol', Subgraphs with restricted degrees of their vertices in planar 3-connected graphs, Graphs Combin. 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] P. Franklin, The four color problem, Amer. J. Math. 44 (1922) 225-236, doi: 10.2307/2370527. Zbl48.0664.02
- [8] B. Grünbaum, New views on some old questions of combinatorial geometry, Int. Teorie Combinatorie, Rome 1 (1976) 451-468.
- [9] J. Harant and S. Jendrol', On the existence of specific stars in planar graph, Graphs and Combinatorics 23 (2007) 529-543, doi: 10.1007/s00373-007-0747-7. Zbl1140.05020
- [10] J. Harant, S. Jendrol' and M. Tkáč, On 3-connected plane graphs without triangular faces, J. Combin. Theory (B) 77 (1999) 150-161, doi: 10.1006/jctb.1999.1918. Zbl1027.05030
- [11] J. van den Heuvel and S. McGuinness, Coloring the square of a planar graph, J. Graph Theory 42 (2003) 110-124, doi: 10.1002/jgt.10077. Zbl1008.05065
- [12] S. Jendrol', Paths with restricted degrees of their vertices in planar graphs, Czechoslovak Math. J. 49 (1999) 481-490, doi: 10.1023/A:1022411100562. Zbl1003.05055
- [13] S. Jendrol', T. Madaras, R. Soták and Z. Tuza, On light cycles in plane triangulations, Discrete Math. 197/198 (1999) 453-467, doi: 10.1016/S0012-365X(99)90099-7. Zbl0936.05065
- [14] S. Jendrol' and H.-J. Voss, Light subgraphs of graphs embedded in the plane and in the projective plane - a survey, P.J. Šafárik University Košice, IM Preprint series (A) No. 1 (2004).
- [15] A. Kotzig, Contribution to the theory of Eulerian polyhedra, Mat. Cas. SAV (Math. Slovaca) 5 (1955) 101-113.
- [16] A. Kotzig, Extremal polyhedral graphs, Ann. New York Acad. Sci. 319 (1979) 565-570.
- [17] H. Lebesgue, Quelques conséquences simples de la formule d'Euler, J. Math. Pures Appl. 19 (1940) 27-43. Zbl0024.28701
- [18] 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
- [19] 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
- [20] W.T. Tutte, A theorem on planar graphs, Trans. Amer. Math. Soc. 82 (1956) 99-116, doi: 10.1090/S0002-9947-1956-0081471-8. Zbl0070.18403
- [21] P. Wernicke, Über den kartographischen Vierfarbensatz, Math. Ann. 58 (1904) 413-426, doi: 10.1007/BF01444968. Zbl35.0511.01

## Citations in EuDML Documents

top## NotesEmbed ?

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