Accession Number:

ADA210289

Title:

On the 2-Extendability of Planar Graphs

Descriptive Note:

Corporate Author:

VANDERBILT UNIV NASHVILLE TN DEPT OF MATHEMATICS

Report Date:

1989-01-01

Pagination or Media Count:

27.0

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 - 22 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.

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE