A Characterization of 3-(γc, 2)-Critical Claw-Free Graphs Which are not 3-γc-Critical
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 Claw-Free Graphs Which are not 3-γc-Critical. Graphs and Combinatorics. 26 (3): pp. 315-328.
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 non-adjacent 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 claw-free 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 k-extendable 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-γc-critical 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 ...