Critical graphs with respect to total domination and connected domination
Abstract
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) < k for every uv /∈ E(G). Further, a ktvc graph is a graph with γt(G) = k and γt (G − v) < k for all v ∈ V(G), where v is not a support vertex (i.e. all neighbors of v have degree greater than one). A 2connected graph G is said to be kcvc if γc(G) = k and γc (G − v) < k for all v ∈ V(G). In this paper, we prove that connected kγt critical graphs and kγccritical graphs are the same if and only if 3 ≤ k ≤ 4. For k ≥ 5, we concentrate on the class of connected kγtcritical graphs G with γc (G) = k and the class of kγccritical graphs G with γt(G) = k. We show that these classes intersect but they do not need to be the same. Further, we prove that 2connected ktvc graphs and kcvc graphs are the same if and only if 3 ≤ k ≤ 4. Similarly, for k ≥ 5, we focus on the class of 2connected ktvc graphs G with γc (G) = k and the class of 2connected kcvc graphs G with γt (G) = k. We finish this paper by showing that these classes do not need to be the same.
Citation
Source Title
School
Collection
Related items
Showing items related by title, author, creator and subject.

Ananchuen, N.; Ananchuen, W.; Caccetta, Louis (2017)A subset S of V (G) is an independent dominating set of G if S is independent and each vertex of G is either in S or adjacent to some vertex of S. Let i(G) denote the minimum cardinality of an independent dominating set ...

Kaemawichanurat, P.; Caccetta, Louis; Ananchuen, W. (2018)© 2018 Charles Babbage Research Centre. All rights reserved. A graph G is said to be kyccritical if the connected domination number yc(G) of G is k and yc(G + uv) < k for every uv ? E(G). The problem of interest for a ...

Ananchuen, Watcharaphong; Ananchuen, Nawarat; Caccetta, Louis (2010)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(γ ...