On the 2-Extendability of Planar Graphs
Abstract
Some sufficient conditions for the 2-extendability of k-connected k-regular (k > or = 3) planar graphs are given. In particular, it is proved that for k > or = 3, a k-connected k-regular planar graph with each cyclic cutset of sufficiently large size is 2-extendable. All graphs in this paper are finite, undirected, connected and simple, although some parallel edge situations will occur after some contractions are made. However, any loops formed by these contractions will be deleted. Let nu and n be positive integers with n < or = (v - 2)/2 and let G be a graph with nu vertices and epsilon edges having a perfect matching. The graph G is said to be n-extendable if every matching of size n in G lies in a perfect matching of G.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1989
- Accession Number
- ADA210289
Entities
People
- D. A. Holton
- Dingjun Lou
- Michael D. Plummer
Organizations
- Vanderbilt University