# zbMATH — the first resource for mathematics

Neighborhood conditions and edge disjoint Hamiltonian cycles. (English) Zbl 0646.05044
Combinatorics, graph theory, and computing, Proc. 18th Southeast. Conf., Boca Raton/Fl. 1987, Congr. Numerantium 59, 55-68 (1987).
[For the entire collection see Zbl 0638.00009.]
A graph G satisfies the neighbourhood condition NC(G)$$\geq m$$, if for every pair of nonadjacent vertices of G, the union of their neighbourhoods has at least m vertices. Let k be a fixed positive integer, and G a graph of order n which satisfies the following four conditions: (1) the minimum degree $$\delta (G)\geq 4k+1;$$ (2) G is 2k- edge-connected; (3) G-v is k-edge-connected for every vertex of G; and $$(4)\quad NC(G)\geq 2(n+C)/3$$ for some $$C=C(k)$$. Then for sufficiently large n, the graph G contains k-edge disjoint Hamiltonian cycles.
The authors point out that if in this case n is even, then G contains 2k- edge disjoint perfect matchings. The authors then establish the following result. Let m be a fixed positive integer and G a graph of even order n that satisfies the following conditions: $$(1)\quad \delta (G)\geq 2m;$$ (ii) G is m-edge-connected; and $$(iii)\quad NC(G)\geq (2n+C)/3$$ for some $$C=C(k)$$. Then for sufficiently large n, the graph G contains m-edge disjoint perfect matchings. The authors also discuss the necessity and sharpness of the conditions in the above two results.
Reviewer: O.Oellermann

##### MSC:
 05C45 Eulerian and Hamiltonian graphs 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C38 Paths and cycles