A characterization of 3-i-critical graphs of connectivity two. Issue 7 (17th November 2017)

• Record Type: Journal Article
• Authors: Ananchuen, N.; Ananchuen, W.; Caccetta, L.
• Is Part Of: Quaestiones mathematicae. Volume 40:Issue 7(2017)
• Page Start: 937
• Page End: 965
• Publication Date: 2017-11-17
• Subjects: 05C69; Independent domination -- critical; Mathematics -- Periodicals; 510.5
• DOI: 10.2989/16073606.2017.1336653
• Languages: English
• ISSNs: 1607-3606

Abstract

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 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 [1] and [2] provide a complete characterization of connected 3- i -critical graphs with a minimum cutset of size at most 3.