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.

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