A Characterization of Independent Domination Critical Graphs with a Cutvertex

Abstract

Let $i(G)$ denote the minimum cardinality of an independent dominating set for $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$. In this paper, we show that if $G$ is a connected $k$-$i$-critical graph, for $k\ge 3$, with a cutvertex $u$, then the number of components of $G–u$, $\omega (G–u)$, is at most $k–1$ and there are at most two non-singleton components. Further, if $\omega (G–u)=k–1$, then a characterization of such graphs is given.