A Characterization of 3(γc, 2)Critical ClawFree Graphs Which are not 3γcCritical
View/Open
Access Status
Fulltext not available
Authors
Ananchuen, Watcharaphong
Ananchuen, Nawarat
Caccetta, Louis
Date
2010Type
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
Collections
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) < ...

Almalki, Norah Saleh A (2016)This thesis investigates diameteredgecritical graphs. Graphs are considered an excellent modelling tool for complex physical systems and many real world problems can be represented by graphs. An important problem that ...