DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click

HERE to register or log in.

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

# Distribution Statement:

## APPROVED FOR PUBLIC RELEASE

#