Matching Extension in Regular Graphs

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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1989
Accession Number
ADA214757

Entities

People

  • M. D. Plummer

Organizations

  • Vanderbilt University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Contracts
  • Decomposition
  • Graph Theory
  • Guarantees
  • Hypotheses
  • Inequalities
  • Mathematics
  • New York
  • Observation
  • Tennessee
  • Universities

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.