
Accession Number : ADA182249
Title : Introduction and Terminology 2Extendability in 3Polytopes.
Descriptive Note : Final rept.,
Corporate Author : VANDERBILT UNIV NASHVILLE TN
Personal Author(s) : Holton, Derek ; Plummer, M D
PDF Url : ADA182249
Report Date : Jan 1985
Pagination or Media Count : 26
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 nextendable 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 3connected (the socalled 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 nextendability became more important when in a previous document it was shown that every 2extendable nonbipartite graph is a brick and that, for n or = 2, every nextendable graph is also (n1)extendable. Thus we have available for study a nested set of subcollections of bicritical graphs.
Descriptors : *GRAPHS, DECOMPOSITION, THEORY, NUMBERS, MATCHING, SIZES(DIMENSIONS)
Subject Categories : Theoretical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE