Introduction and Terminology 2-Extendability in 3-Polytopes.
Abstract
Suppose G is a graph with p points and let n be a positive integer such that P > or = 2n + 2. Graph G is said to be n-extendable if every matching of size n in G extends to a perfect matching. A graph G is called bicritical if G - u - v has a perfect matching, for all pairs of points u,v epsilon V (G). In a canonical decomposition theory for graphs in terms of their maximum (or, when present, perfect) matchings is discussed at length. Bicritical graphs play an important roll in this theory. In particular, those bicritical graphs which are 3-connected (the so-called bricks) currently represent the atoms of the decomposition theory in that no further decomposition of these graphs has been obtained as yet. Indeed at present we seem far from an understanding of the structure of bicritical graphs or even that of bricks. Although interesting in its own right, the study of n-extendability became more important when in a previous document it was shown that every 2-extendable non-bipartite graph is a brick and that, for n > or = 2, every n-extendable graph is also (n-1)-extendable. Thus we have available for study a nested set of subcollections of bicritical graphs.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1985
- Accession Number
- ADA182249
Entities
People
- Derek Holton
- M. D. Plummer
Organizations
- Vanderbilt University