A generalization of domination critical graphs

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75)

Review text

The authors introduce \((\gamma,t)\)-critical graphs as a generalization of domination critical graphs that were defined in 1988 by Brigham, Chinn and Dutton; see \textit{R. C. Brigham, P. Z. Chinn} and \textit{R. D. Dutton} [Networks 18, No. 3, 173-179 (1988; Zbl 0658.05042)]. A graph \(G\) is \((\gamma,t)\)-critical if it has domination number \(\gamma\) and the removal of any set of \(t\) vertices with disjoint neighbourhoods produces a graph with domination number \(\gamma-t\). Using this notation the domination critical graphs are exactly the \((\gamma,1)\)-critical graphs. The authors show the existence of \((\gamma,t)\)-critical graphs for any positive integers \(t\leq \gamma\) and characterize \((\gamma,t)\)-critical graphs for \(t\in \{ \gamma,\gamma-1\}\). Then they show that no tree is \((\gamma,t)\)-critical and that a unicyclique graph is \((\gamma,t)\)-critical for some \(t\leq \gamma\) if and only if it is a domination critical cycle or the corona graph \(K_3\circ K_1\). Some open problems are posed.

Recommendations

Cited in

(20)

This page was built for publication: A generalization of domination critical graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2707955)