# DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

# IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

# Discussiones Mathematicae Graph Theory

## 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) ≤ 32 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.