Accession Number:

ADA214757

Title:

Matching Extension in Regular Graphs

Descriptive Note:

Corporate Author:

VANDERBILT UNIV NASHVILLE TN DEPT OF MATHEMATICS

Personal Author(s):

Report Date:

1989-01-01

Pagination or Media Count:

17.0

Abstract:

This paper deals with extending matching in regular graphs. There are two main results. The first presents a sufficient condition in terms of cyclic connectivity for extending matching in regular bipartite graphs. This theorem generalizes an earlier result due to Holton and the author. The second result deals with regular-but not necessarily bipartite-graphs. In this case, it is known that a result analogous to that obtained in the bipartite case is impossible, but a new proof is given of a result of Naddef and Pulleyblank which guarantees that a regular graph with an even number of points which has sufficiently large cyclic connectivity will be bicritical. Algorithms. jes

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE