A characterization of 3-i-critical graphs of connectivity two

Published in: Quaestiones Mathematicae
Volume 40, issue 7, 2017, pages: 937–965
DOI: 10.2989/16073606.2017.1336653
Author(s): N. AnanchuenDepartment of Mathematics, Faculty of Science, Thailand, W. AnanchuenSchool of Liberal Arts, Thailand, L. CaccettaWestern Australian Centre of Excellence in Industrial Optimisation, Department of Mathematics and Statistics, Western Australia
Keywords: 05C69, 05C69


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

Get new issue alerts for Quaestiones Mathematicae