The Cartesian Product of a k-Extendable and an l-Extendable Graph is (k + l +1)-Extendable
Abstract
Let us start with the definition of a kappa-extendable graph G. Suppose kappa is an integer such that 1 < or = kappa < or = (/V(G)/-2)/2. A graph G is kappa-extendable if G is connected, has a perfect matching (a 1- factor) and any matching in G consisting of kappa edges can be extended to (i.e. , is a subset of) a perfect matching. The extendability number of G, extG, is the maximum kappa such that G is kappa-extendable. A natural problem is to determine the extendability number of a graph G.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1991
- Accession Number
- ADA248191
Entities
People
- E. Gyori
- M. D. Plummer
Organizations
- Vanderbilt University