On i−-ER-critical graphs Original Research Article

We are interested in the behaviour of the independent domination number i(G) of a graph G under edge deletion, and in particular in i−-ER-critical graphs, i.e., graphs for which i(G) decreases whenever an edge e is removed. If γ(G) denotes the domination number of G, we determine all the i−-ER-critical graphs G such that γ(G)=2 and i(G−e)=2 for every edge e of G. Different classes of i−-ER-critical graphs such that i(G−e)>γ(G) for all or some edges e are described. Finally, for a particular family of circulants, we find the exact value of i(G−e) for every edge e of the graphs of this family and obtain as a corollary the number of automorphism classes of their edge sets.