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
2010Type
Journal Article
Metadata
Show full item recordCitation
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
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.
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)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 set if G[D] is connected. The minimum cardinality of a ...