This paper introduces the notion of $(\iota,q)$-critical graphs. The isolation number of a graph $G$, denoted by $\iota(G)$ and also known as the vertex-edge domination number, is the minimum number of vertices in a set $D$ such that the subgraph induced by the vertices not in the closed neighbourhood of $D$ has no edges. A graph $G$ is $(\iota,q)$-critical, $q \ge 1$, if the subdivision of any $q$ edges in $G$ gives a graph with isolation number greater than $\iota(G)$ and there exists a set of $q-1$ edges such that subdividing them gives a graph with isolation number equal to $\iota(G)$. We prove that for each integer $q \ge 1$ there exists a $(\iota,q)$-critical graph, while for a given graph $G$, the admissible values of $q$ satisfy $1 \le q \le |E(G)| - 1$. In addition, we provide a general characterisation of $(\iota,1)$-critical graphs as well as a constructive characterisation of $(\iota,1)$-critical trees.
Categories: math.CO cs.DM cs.DS