[@Payan1980]. Loosely speaking, these are the graphs for which the characteristic vectors of the minimal dominating sets are the zero-one solutions of a linear equality. Formally, equidominating graphs have the following definition.

A graph $G=(V,E)$ is called *equidominating* if there exists a value $t\in{\ensuremath{\mathbb{N}}}= \{1,2,3,\ldots\}$ and a weight function ${\omega}\colon V \rightarrow {\ensuremath{\mathbb{N}}}$ such that for all $D\subseteq V$ the following equivalence holds: $$D \text{ is an mds } \iff {\omega}(D) := \sum_{v\in D}{{\omega}(v)} = t.$$ The pair $({\omega},t)$ is called an *equidominating structure*, ${\omega}$ an *equidominating function* and $t$ a *target value*.

Figure \[fig:example\_equidom\_graph\] shows an equidominating graph. Every mds has a total weight of 23 and further, every subset of weight 23 is an mds.

\[fig:example\_equidom\_graph\]

(-3,-1)(13,6)

(2,4)[a]{}[$a$]{} (4,0)[b]{}[$b$]{} (8,5)[c1]{}[$c_1$]{} (8,2)[c2]{}[$c_2$]{} (0,1)[d]{}[$d$]{} (12,0)[e]{}[$e$]{} (-2,5)[s1]{}[$s_1$]{} (-2,3)[s2]{}[$s_2$]{}

One advantage of having an equidominating structure of the graph at hand is that one can check whether a given vertex subset is an mds in linear time.

The [Equidomination]{} problem is to decide whether a given graph is equidominating or not. Unfortunately, the computational complexity of this problem is unknown. It is not even clear whether [Equidomination]{} is in NP.

It can be seen that the following problem is coNP-complete: given a 