PDF
Discussiones Mathematicae Graph Theory 28(3) (2008)
441-451
DOI: https://doi.org/10.7151/dmgt.1418
ON LONG CYCLES THROUGH FOUR PRESCRIBED VERTICES OF A POLYHEDRAL GRAPH
Jochen Harant1, Stanislav Jendrol'2 and Hansjoachim Walther1
1Institute of Mathematics
Technical University Ilmenau, Germany
2Institute of Mathematics
P.J. Safárik University Košice, Slovakia
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.Keywords: graph, long cycle, prescribed vertices.
2000 Mathematics Subject Classification: 05C38.
References
[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. |
[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. |
[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. |
[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. |
[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. |
[8] | W.T. Tutte, Bridges and Hamiltonian circuits in planar graphs, Aequationes Math. 15 (1977) 1-33, doi: 10.1007/BF01837870. |
Received 31 July 2007
Revised 3 June 2008
Accepted 3 June 2008
Close