Nothing Special   »   [go: up one dir, main page]

DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2023): 0.5

5-year Journal Impact Factor (2023): 0.6

CiteScore (2023): 2.2

SNIP (2023): 0.681

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 28(1) (2008) 121-135
DOI: https://doi.org/10.7151/dmgt.1396

PATHS OF LOW WEIGHT IN PLANAR GRAPHS

Igor Fabrici1, Jochen Harant2  and  Stanislav Jendrol'1

1Institute of Mathematics
P.J. Safárik University
Jesenná 5, SK-04154 Košice, Slovak Republic
e-mail: stanislav.jendrol@upjs.sk,  igor.fabrici@upjs.sk

2Institute of Mathematics
Ilmenau Technical University
PF 10 05 65, D-98684 Ilmenau, Germany
e-mail: harant@mathematik.tu-ilmenau.de

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

wG(P): =
∑
 u ∈ V(P) 
 degG(u) ≤ 3
2
  k2+O(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) ≤ k2+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 .
Keywords: planar graphs, polytopal graphs, paths, weight of an edge, weight of a path.

2000 Mathematics Subject Classification: 05C10, 05C38, 52B10.

References

[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.
[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.
[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.
[5] I. Fabrici and S. Jendrol', Subgraphs with restricted degrees of their vertices in planar 3-connected graphs, Graphs Combin. 13 (1997) 245-250.
[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.
[7] P. Franklin, The four color problem, Amer. J. Math. 44 (1922) 225-236, doi: 10.2307/2370527.
[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.
[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.
[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.
[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.
[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.
[14] S. Jendrol' and H.-J. Voss, Light subgraphs of graphs embedded in the plane and in the projective plane - a survey, P.J. Safá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.
[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.
[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.
[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.
[21] P. Wernicke, Über den kartographischen Vierfarbensatz, Math. Ann. 58 (1904) 413-426, doi: 10.1007/BF01444968.

Received 22 November 2006
Revised 4 May 2007
Accepted 4 May 2007

Close