A characterization of 3icritical graphs of connectivity two
Access Status
Authors
Date
2017Type
Metadata
Show full item recordCitation
Source Title
ISSN
School
Collection
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.
Related items
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 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. ...