Matching Extension in Bipartite Graphs. 1. Introduction and Terminology,
Abstract
All graphs in this paper will be finite and connected and will have no loops or parallel lines. Let n and p be positive integers with n < or = (p - 2)/2 and let G be a graph with p points having a perfect matching. Graph G is said to be n-extendable if every matching of size n in G extends to a perfect matching. This paper is concerned primarily with studying n-extendability in bipartite graphs. In the first section of this paper the author gathers together the various characterizations of 1-extendable bipartite graphs mentioned above and then give the natural generalizations to n-extendability with a unified proof of the equivalencies. In another paper the author presented some results on the connectivity of general n-extendable graphs. In the second section of this paper proves a result about connectivity which is peculiar to the bipartite case.
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1986
- Accession Number
- ADA168666
Entities
People
- M. D. Plummer
Organizations
- Vanderbilt University