Neighborhood conditions and edge-disjoint perfect matchings. (English) Zbl 0769.05073

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.


05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C99 Graph theory
Full Text: DOI


[1] Anderson, I., Perfect matchings of a graph, J. Combin. Theory Ser. B, 10, 183-186 (1971) · Zbl 0172.48904
[2] Faudree, R. J.; Gould, R. J.; Jacobson, M. S.; Schelp, R. H., Extremal problems involving neighborhood unions, J. Graph Theory, 4, 555-564 (1987) · Zbl 0659.05058
[3] Faudree, R. J.; Gould, R. J.; Schelp, R. H., Neighborhood conditions and edge disjoint hamiltonian cycles, Congr. Numer., 59, 55-68 (1987) · Zbl 0646.05044
[5] Hall, P., On representations of subsets, J. London Math. Soc., 10, 26-30 (1935) · Zbl 0010.34503
[6] Jackson, W., Hamilton cycles in regular 2-connected graphs, J. Combin. Theory Ser. B, 29, 27-46 (1980) · Zbl 0377.05027
[7] Kovari, T.; Sós, V. T.; Túran, P., On a problem of Zarankiewicz, Colloq. Math., 3, 50-57 (1954) · Zbl 0055.00704
[8] Tutte, W. T., A short proof of the factor theorem for finite graphs, Canad. J. Math., 6, 347-352 (1954) · Zbl 0055.17102
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.