A Characterization of 3-(gamma(c), 2)-Critical Claw-Free Graphs Which are not 3-gamma(c)-Critical

作者：Ananchuen Watcharaphong; Ananchuen Nawarat^*; Caccetta Louis

来源：Graphs and Combinatorics, 2010, 26(3): 315-328.

DOI：10.1007/s00373-010-0920-2

• Connected domination
• Critical graph
• Claw-free

Let gamma(c)(G) denote the minimum cardinality of a connected dominating set for G. A graph G is k-gamma(c)- critical if gamma(c)(G) = k, but gamma(c)(G + xy) < k for xy epsilon E(<(G)over bar>). Further, for integer r >= 2, G is said to be k-(gamma(c), r)-critical if gamma(c)(G) = k, but gamma(c)(G )+ xy) < k for each pair of non-adjacent vertices x and y that are at distance most r apart. k-gamma(c)- critical graphs are k-(gamma(c), r)- critical but the converse need not be true.

• 出版日期2010-5