Matchings in 3-vertex-critical graphs: The even case
A subset of vertices D of a graph G is a dominating set for G if every vertex of G not in D is adjacent to one in D. The cardinality of any smallest dominating set in G is denoted by gamma(G) and called the domination number of G. Graph G is said to be gamma-vertex-critical if gamma(G - v) < gamma(G), for every v vertex in G. Comparatively little is known to date about the structure of gamma-vertex-critical graphs, even in the case when gamma = 3. In the present article, we begin the study of matchings in 3-vertex-critical graphs. In particular, we show that any 3-vertex-critical graph on an even number of vertices, which has no induced subgraph isomorphic to the bipartite graph K-1,K-5 much have a perfect matching, whereas 3-vertex-critical even graphs in general need not contain such a matching. We close with a conjecture. (c) 2005 Wiley Periodicals, Inc.
domination perfect matching vertex-critical