A characterization of 3-i-critical graphs of connectivity two
MetadataShow full item record
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 of G. A graph G is k-i-critical if i(G) = k, but i(G + uv) < k for any pair of non-adjacent vertices u and v of G. The problem that arises is that of characterizing k-i critical graphs. In this paper, we characterize connected 3-i-critical graphs with minimum vertex cutset of size 2. More specifically, we show that if G is a connected 3-i-critical graph with minimum vertex cutset S of size 2 and the number of components of G - S is exactly two, then G is isomorphic to a graph in one of nine classes of connected 3-i-critical graphs. The results in this paper together with results in  and  provide a complete characterization of connected 3-i-critical graphs with a minimum cutset of size at most 3.
Showing items related by title, author, creator and subject.
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 ...
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 ...
Ananchuen, N.; Ruangthampisan, S.; Ananchuen, W.; Caccetta, Louis (2018)© 2018, University of Queensland. All rights reserved. Let ? i (G) denote the independent domination number of G. A graph G is said to be k-? i -vertex-critical if ? i (G) = k and for each x ? V (G), ? i (G - x) < k. ...