Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650013 | Discrete Mathematics | 2009 | 5 Pages |
Abstract
A vertex subset SS of a graph GG is a dominating set if every vertex of GG either belongs to SS or is adjacent to a vertex of SS. The cardinality of a smallest dominating set is called the dominating number of GG and is denoted by γ(G)γ(G). A graph GG is said to be γγ-vertex-critical if γ(G−v)<γ(G)γ(G−v)<γ(G), for every vertex vv in GG.Let GG be a 2-connected K1,5K1,5-free 3-vertex-critical graph of odd order. For any vertex v∈V(G)v∈V(G), we show that G−vG−v has a perfect matching (except two graphs), which solves a conjecture posed by Ananchuen and Plummer [N. Ananchuen, M.D. Plummer, Matchings in 3-vertex critical graphs: The odd case, Discrete Math., 307 (2007) 1651–1658].
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Tao Wang, Qinglin Yu,