Neighborhood conditions and edge-disjoint perfect matchings (Q1179275)

A graph \(G\) satisfies the all pairs neighborhood condition \(\text{ANC}(G)\geq m\) if, for each pair \(x,y\) of vertices of \(G\), we have \(| N_ G(x)\cup N_ G(y)|\geq m\). Let \(k\) be a fixed positive integer and \(G\) a graph of even order \(n\) which satisfies the following conditions: (1) the minimum degree of \(G\) is at least \(k+1\); (2) the edge-connectivity of \(G\) is at least \(k\) and (3) \(\text{ANC}(G)\geq n/2\). Then it is shown that for sufficiently large \(n\), \(G\) contains \(k\) edge- disjoint perfect matchings. It is also shown that each of the conditions (1), (2) and (3) is necessary for \(G\) to contain \(k\) edge-disjoint perfect matchings.