Matchings in 3‐vertex‐critical graphs: The even case
Nawarat Ananchuen, Michael D. Plummer · Networks · 2005
Abstract 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 γ(G)and called the domination number of G. Graph G is said to be γ‐vertex‐critical if γ(G − v) < γ(G), for every v vertex in G. Comparatively little is known to date about the structure of γ‐vertex‐critical graphs, even in the case when γ = 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 K1,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. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(4), 210–213 2005