A characterization of 3icritical graphs of connectivity two
Abstract
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
ISSN
School
Collection
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 ...

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 vertexcritical if ? i (G) = k and for each x ? V (G), ? i (G  x) < k. ...

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) < ...