A characterization of 3icritical graphs of connectivity two
Access Status
Authors
Date
2017Collection
Type
Metadata
Show full item recordAbstract
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 kicritical if i(G) = k, but i(G + uv) < k for any pair of nonadjacent vertices u and v of G. The problem that arises is that of characterizing ki critical graphs. In this paper, we characterize connected 3icritical graphs with minimum vertex cutset of size 2. More specifically, we show that if G is a connected 3icritical 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 3icritical graphs. The results in this paper together with results in [1] and [2] provide a complete characterization of connected 3icritical graphs with a minimum cutset of size at most 3.
Citation
Source Title
Department
Related items
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 kextendable 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γccritical 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. ...