PL EN

Preferencje
Język
Widoczny [Schowaj] Abstrakt
Liczba wyników
Czasopismo

## Discussiones Mathematicae Graph Theory

2008 | 28 | 1 | 121-135
Tytuł artykułu

### Paths of low weight in planar graphs

Autorzy
Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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$.
Słowa kluczowe
EN
Kategorie tematyczne
Wydawca
Czasopismo
Rocznik
Tom
Numer
Strony
121-135
Opis fizyczny
Daty
wydano
2008
otrzymano
2006-11-22
poprawiono
2007-05-04
zaakceptowano
2007-05-04
Twórcy
autor
• Institute of Mathematics, P.J. Šafárik University, Jesenná 5, SK-04154 Košice, Slovak Republic
autor
• Institute of Mathematics, Ilmenau Technical University, PF 10 05 65, D-98684 Ilmenau, Germany
autor
• Institute of Mathematics, P.J. Šafárik University, Jesenná 5, SK-04154 Košice, Slovak Republic
Bibliografia
• [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. Š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.
• [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.
Typ dokumentu
Bibliografia
Identyfikatory