Critical graphs with respect to total domination and connected domination
MetadataShow full item record
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) < k for every uv /∈ E(G). Further, a k-tvc 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 2-connected graph G is said to be k-cvc 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-γc-critical graphs are the same if and only if 3 ≤ k ≤ 4. For k ≥ 5, we concentrate on the class of connected k-γt-critical graphs G with γc (G) = k and the class of k-γc-critical 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 2-connected k-tvc graphs and k-cvc graphs are the same if and only if 3 ≤ k ≤ 4. Similarly, for k ≥ 5, we focus on the class of 2-connected k-tvc graphs G with γc (G) = k and the class of 2-connected k-cvc graphs G with γt (G) = k. We finish this paper by showing that these classes do not need to be the same.
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 k-yc-critical 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 ...
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 ...