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

Abstract

top
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 ) d e g 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 ) d e g 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 ) d e g G ( u ) ≤ ( 3 / σ + 3 ) k .

How to cite

top

Igor 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. [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. [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. [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. [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. [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. [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. [7] P. Franklin, The four color problem, Amer. J. Math. 44 (1922) 225-236, doi: 10.2307/2370527. Zbl48.0664.02
  8. [8] B. Grünbaum, New views on some old questions of combinatorial geometry, Int. Teorie Combinatorie, Rome 1 (1976) 451-468. 
  9. [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. [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. [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. [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. [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. [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. [15] A. Kotzig, Contribution to the theory of Eulerian polyhedra, Mat. Cas. SAV (Math. Slovaca) 5 (1955) 101-113. 
  16. [16] A. Kotzig, Extremal polyhedral graphs, Ann. New York Acad. Sci. 319 (1979) 565-570. 
  17. [17] H. Lebesgue, Quelques conséquences simples de la formule d'Euler, J. Math. Pures Appl. 19 (1940) 27-43. Zbl0024.28701
  18. [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. [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. [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. [21] P. Wernicke, Über den kartographischen Vierfarbensatz, Math. Ann. 58 (1904) 413-426, doi: 10.1007/BF01444968. Zbl35.0511.01

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.