On Independent Domination Critical Graphs and \(k\)-Factor Critical Graphs

Abstract

A subset \(S \subseteq V(G)\) is an independent dominating set for \(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 for \(G\). For a positive integer \(t\), a graph \(G\) is \(t\)-i-critical if \(i(G) = t\), but \(i(G + uv) < t\) for any pair of non-adjacent vertices \(u\) and \(v\) of \(G\). Further, for a positive integer \(k\), a graph \(G\) is \(k\)-factor-critical if for every \(S \subseteq V(G)\) with \(|S| = k\), \(G – S\) has a perfect matching. In this paper, we provide sufficient conditions for connected \(3\)-i-critical graphs to be \(k\)-factor-critical in terms of connectivity and minimum degree.