A Characterization of 3(γc, 2)Critical ClawFree Graphs Which are not 3γcCritical
Abstract
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
ISSN
School
Department of Mathematics and Statistics
Collection
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) < ...

Kaemawichanurat, P.; Caccetta, Louis; Ananchuen, N. (2018)© Charles Babbage Research Centre. All rights reserved. A vertex subset D of G is a dominating set of G if every vertex in V(G)D is adjacent to a vertex in D. Moreover, a dominating set D of G is a connected dominating ...