Neighborhood conditions and edge-disjoint perfect matchings

✍ Scribed by R.J. Faudree; R.J. Gould; L.M. Lesniak

• Publisher: Elsevier Science
• Year: 1991
• Tongue: English
• Weight: 667 KB
• Volume: 91
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(91)90160-4

✦ Synopsis

Neighborhood conditions and edge-disjoint perfect matchings, Discrete Mathematics 91 (1991) 33-43. A graph G satisfies the neighborhood condition ANC(G) 2 m if, for all pairs of vertices of G, the union of their neighborhoods has at least m vertices. For a fixed positive integer k, let G be a graph of even order n which satisfies the following conditions: 6(G) 2 k + 1; x,(G) 2 k; and ANC(G) 2 n/2. It is shown that if n is sufficiently large then G contains k edge-disjoint perfect matchings.

A matching in a graph is a set of edges of which no two have a common incident vertex. An s-matching is a matching with s edges and a perfect matching in a graph of order n is a matching with n/2 edges. The classic theorem of Tutte [S] characterizing those graphs with perfect matchings states that a nontrivial graph G has a perfect matching if and only if, for every proper subset S of V(G), the number of components of G -S with an odd number of vertices is at most ISI. Anderson's proof of Tutte's Theorem [I] employs Hall's Theorem [5], one form of which can be stated as: Let G be a bipartite graph with partite sets VI and V,, where IV,1 = IV,l. Then G contains a perfect matching if and only if for every subset S of VI, INAm 2 ISI, where NG(S) denotes the set of all vertices adjacent to at least one vertex of S.