GRAPHS WITH EVERY PATH OF LENGTH k IN A HAMILTONIAN CYCLE

Grzegorz Gancarzewicz

Abstrakt

In this paper we prove that if G is a (k + 2)-connected graph on n > 3 vertices satisfying
P(n + k) :
dG(x; y) = 2 ) maxfd(x); d(y)g > n + k
2
for each pair of vertices x and y in G; then any path S  G of length k is contained in a
hamiltonian cycle of G:

Słowa kluczowe: cycle, graph, hamiltonian cycle, matching, path
References

A. Benhocine and A.P. Wojda, The Geng-Hua Fan conditions for pancyclic or hamiltonian-connected graphs, J. Combin. Theory Ser. B 42, 1985, 167—180.

J.A. Bondy and V. Chvátal, A method in graph theory, Discrete Math. 15, 1976, 111—135.

J.A. Bondy and U.S.R. Murty, Graph theory with applications, The Macmillan Press LTD London 1976.

G. Fan, New sufficient conditions for cycles in graphs, J. Combin. Theory Ser. B 37, 1984, 221—227.

G. Gancarzewicz and A.P. Wojda, Graphs with every k-matching in a hamiltonian cycle, Discrete Math. 213, 2000, 141 — 151.

R. H˝aggkvist, On F-hamiltonian graphs in Graph Theory and Related Topics, ed. J.A. Bondy and U.S.R. Murty, Academic Press N.Y. 1979, 219—231.

H.V. Kronk, Variations of a theorem of Pósa in The Many Facets of Graph Theory, ed. G. Chartrand and S.F. Kapoor, Lect. Notes Math. 110, Springer Verlag 1969, 193—197.

M. Las Vergnas, Sur une propriété des arbres maximaux dans un graphe, C. R. Axad. Sci. Paris, Sér. A, 272, 1971, 1297—1300.

O. Ore, Note on hamiltonian circuits, Amer. Math. Monthly 67, 1960, 55.

Z. Skupien and A.P. Wojda, On highly hamiltonian graphs, Bull. Acad. Polon. Sci., Sér. Sci. Math. Astronom. Phys. 22, 1974, 463—471.

A.P. Wojda, Hamiltonian cycles through matchings, Demonstratio Mathematica XXI 2, 1983, 547—553.