# On long cycles through four prescribed vertices of a polyhedral graph

Jochen Harant; Stanislav Jendrol'; Hansjoachim Walther

Discussiones Mathematicae Graph Theory (2008)

- Volume: 28, Issue: 3, page 441-451
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topJochen Harant, Stanislav Jendrol', and Hansjoachim Walther. "On long cycles through four prescribed vertices of a polyhedral graph." Discussiones Mathematicae Graph Theory 28.3 (2008): 441-451. <http://eudml.org/doc/270764>.

@article{JochenHarant2008,

abstract = {For a 3-connected planar graph G with circumference c ≥ 44 it is proved that G has a cycle of length at least (1/36)c+(20/3) through any four vertices of G.},

author = {Jochen Harant, Stanislav Jendrol', Hansjoachim Walther},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {graph; long cycle; prescribed vertices},

language = {eng},

number = {3},

pages = {441-451},

title = {On long cycles through four prescribed vertices of a polyhedral graph},

url = {http://eudml.org/doc/270764},

volume = {28},

year = {2008},

}

TY - JOUR

AU - Jochen Harant

AU - Stanislav Jendrol'

AU - Hansjoachim Walther

TI - On long cycles through four prescribed vertices of a polyhedral graph

JO - Discussiones Mathematicae Graph Theory

PY - 2008

VL - 28

IS - 3

SP - 441

EP - 451

AB - For a 3-connected planar graph G with circumference c ≥ 44 it is proved that G has a cycle of length at least (1/36)c+(20/3) through any four vertices of G.

LA - eng

KW - graph; long cycle; prescribed vertices

UR - http://eudml.org/doc/270764

ER -

## References

top- [1] T. Böhme, F. Göring and J. Harant, Menger's theorem, J. Graph Theory 37 (2001) 35-36, doi: 10.1002/jgt.1001. Zbl0988.05057
- [2] R. Diestel, Graph Theory (Springer, Graduate Texts in Mathematics 173, 2000).
- [3] A.K. Kelmans and M.V. Lomonosov, When m vertices in a k-connected graph cannot be walked round along a simple cycle, Discrete Math. 38 (1982) 317-322, doi: 10.1016/0012-365X(82)90299-0. Zbl0475.05053
- [4] L. Lovász, Combinatorial problems and exercises (Akadémiai Kiadó, Budapest, Hungary 1979) Section 6, Problem 42.
- [5] J.W. Moon and L. Moser, Simple paths on polyhedra, Pacific J. Math. 13 (1963) 629-631. Zbl0115.41001
- [6] A. Saito, Long cycles through specified vertices in a graph, J. Combin. Theory (B) 47 (1989) 220-230, doi: 10.1016/0095-8956(89)90021-X. Zbl0686.05031
- [7] 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
- [8] W.T. Tutte, Bridges and Hamiltonian circuits in planar graphs, Aequationes Math. 15 (1977) 1-33, doi: 10.1007/BF01837870. Zbl0357.05039

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.