CYCLES CONTAINING SPECIFIED EDGES IN A GRAPH

Grzegorz Gancarzewicz

Abstrakt

The aim of this paper is to prove that if s > 1 and G is a graph of order n > 4s + 6 satisfying
2 > (4n - 4s - 3) / 3 ; then every matching of G lies on a cycle of length at least n-s and hence, in a path of length at least n - s + 1:

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

Berman K.A., Proof of a conjecture of Haggkvist on cycles and independent edges, Discrete Mathematics 46, 1983, 9—13.

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

Chvátal V., On Hamilton’s ideals, J. Combin. Theory B 12, 1972, 163—168.

Häggkvist R., 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.

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

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