A Characterization of 3(γc, 2)Critical ClawFree Graphs Which are not 3γcCritical
Access Status
Fulltext not available
Authors
Ananchuen, Watcharaphong
Ananchuen, Nawarat
Caccetta, Louis
Date
2010Collection
Type
Journal Article
Metadata
Show full item recordAbstract
Let γ c (G) denote the minimum cardinality of a connected dominating set for G. A graph G is kγ c critical if γ c (G) = k, but γ c (G + xy) < k for xy Î E([`(G)])xyE(G) . Further, for integer r ≥ 2, G is said to be k(γ c , r)critical if γ c (G) = k, but γ c (G + xy) < k for each pair of nonadjacent vertices x and y that are at distance at most r apart. kγ c critical graphs are k(γ c , r)critical but the converse need not be true. In this paper, we give a characterization of 3(γ c , 2)critical clawfree graphs which are not 3γ c critical. In fact, we show that there are exactly four classes of such graphs.
Citation
Ananchuen, Watcharaphong and Ananchuen, Nawarat and Caccetta, Louis. 2010. A Characterization of 3(γc, 2)Critical ClawFree Graphs Which are not 3γcCritical. Graphs and Combinatorics. 26 (3): pp. 315328.
Source Title
Graphs and Combinatorics
Department
Department of Mathematics and Statistics
Related items
Showing items related by title, author, creator and subject.

Ananchuen, Nawarat (1994)Let G be a simple connected graph on 2n vertices with a perfect matching. For 1 ≤ k ≤ n  1, G is said to be kextendable if for every matching M of size k in G there is a perfect matching in G containing all the edges ...

Kaemawichanurat, P.; Caccetta, Louis; Ananchuen, N. (2016)A graph G is said to be kγt critical if the total domination number γt(G)= k and γt (G + uv) < k for every uv /∈ E(G). A kγccritical graph G is a graph with the connected domination number γc(G) = k and γc(G + uv) < ...

Ananchuen, N.; Ananchuen, W.; Caccetta, Louis (2017)© 2017 NISC (Pty) Ltd. A subset S of V (G) is an independent dominating set of G if S is independent and each vertex of G is either in S or adjacent to some vertex of S. Let i(G) denote the minimum cardinality of an ...