×

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