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.
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 ...
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-γc-critical graph G is a graph with the connected domination number γc(G) = k and γc(G + uv) < ...
Lam, Bee K. (1999)A network is a system that involves movement or flow of some commodities such as goods and services. In fact any structure that is in the form of a system of components some of which interact can be considered as a network. ...