Paths of low weight in planar graphs
Igor Fabrici ; Jochen Harant ; Stanislav Jendrol'
Discussiones Mathematicae Graph Theory, Tome 28 (2008), p. 121-135 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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 wG(P):=∑u∈V(P)degG(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 wT(P):=∑u∈V(P)degT(u)≤k²+13k 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 wG(P)=∑u∈V(P)degG(u)≤(3/σ+3)k.

Publié le : 2008-01-01
EUDML-ID : urn:eudml:doc:270221 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1396,
     author = {Igor Fabrici and Jochen Harant and Stanislav Jendrol'},
     title = {Paths of low weight in planar graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {28},
     year = {2008},
     pages = {121-135},
     zbl = {1155.05010},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1396}
}

Igor Fabrici; Jochen Harant; Stanislav Jendrol'. Paths of low weight in planar graphs. Discussiones Mathematicae Graph Theory, Tome 28 (2008) pp. 121-135. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1396/

[000] [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.

[001] [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. | Zbl 1025.05036

[002] [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. | Zbl 0307.05107

[003] [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 | Zbl 0916.05020

[004] [5] I. Fabrici and S. Jendrol', Subgraphs with restricted degrees of their vertices in planar 3-connected graphs, Graphs Combin. 13 (1997) 245-250. | Zbl 0891.05025

[005] [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. | Zbl 0956.05059

[006] [7] P. Franklin, The four color problem, Amer. J. Math. 44 (1922) 225-236, doi: 10.2307/2370527. | Zbl 48.0664.02

[007] [8] B. Grünbaum, New views on some old questions of combinatorial geometry, Int. Teorie Combinatorie, Rome 1 (1976) 451-468.

[008] [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. | Zbl 1140.05020

[009] [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. | Zbl 1027.05030

[010] [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. | Zbl 1008.05065

[011] [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. | Zbl 1003.05055

[012] [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. | Zbl 0936.05065

[013] [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).

[014] [15] A. Kotzig, Contribution to the theory of Eulerian polyhedra, Mat. Cas. SAV (Math. Slovaca) 5 (1955) 101-113.

[015] [16] A. Kotzig, Extremal polyhedral graphs, Ann. New York Acad. Sci. 319 (1979) 565-570.

[016] [17] H. Lebesgue, Quelques conséquences simples de la formule d'Euler, J. Math. Pures Appl. 19 (1940) 27-43. | Zbl 0024.28701

[017] [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. | Zbl 0934.05079

[018] [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 | Zbl 0946.05034

[019] [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. | Zbl 0070.18403

[020] [21] P. Wernicke, Über den kartographischen Vierfarbensatz, Math. Ann. 58 (1904) 413-426, doi: 10.1007/BF01444968. | Zbl 35.0511.01