Equitable graph of a graph (Q2869949)

Starting from the concept of a dominating set of a graph \(G = V \cup E\), the author defines a set \(D\) to be an equitable dominating set if it is: a) dominating and b) for every \(v \in V - D\) there is a \(u \in D\) adjacent to \(v\) such that \(|d(u) - d(v)| \leq 1\). NEWLINENEWLINENEWLINE \(\delta^e(G)\) denotes the size of a smallest equitable dominating set in \(G\). Two vertices of \(G\) are said to be degree-equitable if their degrees differ by at most \(1\).NEWLINENEWLINEThe equitable graph \(G^e\) of \(G = V \cup E\) has \(V(G^e) = V\) and for \(u,v \in V\) one has \(uv \in E(G^e)\) iff \(u\) and \(v\) are degree-equitable.NEWLINENEWLINEThese definitions imply \(\delta(G^e) \leq \delta^e(G)\) where \(\delta(H)\) is the domination number of \(H\); and equality holds if for all \(u \in V\) in \(G\) the vertices equitable with \(u\) are adjacent to \(u\). However, the converse is not true in general. On the other hand, \(\delta(G^e) < \delta^e(G)\) iff for any minimum dominating set \(D\) of \(G^e\) there is a vertex \(u \in V - D\) such that no neighbor of \(u\) in \(G^e\) which is also a neighbor of \(u\) in \(G\), lies in \(D\).NEWLINENEWLINEMoreover, \(\delta(G) = \delta^e(G)\) iff \(G\) has a minimum dominating set \(D\) such that for every \(u \in V - D\) at least one of its neighbors in \(G\) is degree-equitable and lies in \( D\). On the other hand, in general, \(\delta^e(G) - \delta(G)\) can be arbitrarily large (see, e.g., \(K_{1,r}\)). The author also exhibits classes of graphs where \(\delta = \delta^e\).