Characterizations of minimal dominating sets and the well-dominated property in lexicographic product graphs

NEW

Problem: For finite simple undirected graphs $G$, reconstruct Problem 7.1 as follows. A dominating set $D\subseteq V(G)$ is reducible if some $u\in D$ satisfies that $D\setminus\{u\}$ is still dominating and

$$N(D\setminus\{u\})=N(D).$$

Otherwise $D$ is irreducible. Characterize graphs $G$ such that every irreducible dominating set is either an inclusion-minimal dominating set or an inclusion-minimal total dominating set. This matches the definitions and terminology in Gözüpek–Hujdurović–Milanič.

Result: For $M\subseteq V(G)$, write

$$\operatorname{Iso}(M)=\{m\in M:N(m)\cap M=\varnothing\},$$

and for $m\in M$,

$$P_M(m)=\{v\in V(G):N[v]\cap M=\{m\}\}.$$

For a minimal dominating set $M$ and a vertex $x\notin M$, put $D=M\cup\{x\}$ and

$$L(M,x)=\{y\in D: |N(y)\cap D|=1\},$$

the set of leaves of $G[D]$.

Then $G$ has the required property if and only if the following condition holds:

For every minimal dominating set $M$ and every $x\notin M$, if

1. $N(x)\cap L(M,x)\neq\varnothing$, and
2. for every $m\in M$ with $P_M(m)\subseteq N[x]$, one has $N(m)\cap L(M,x)\neq\varnothing$,

then

$$\operatorname{Iso}(M)\subseteq N(x).$$

Equivalently: the forbidden certificates are exactly pairs $(M,x)$ where $M$ is minimal dominating, $x\notin M$, $M\cup\{x\}$ is irreducible, and some isolated vertex of $G[M]$ is not adjacent to $x$.

Proof sketch. A dominating set $D$ is irreducible iff every $u\in D$ either has a $D$-private closed neighbor or is adjacent to a leaf of $G[D]$. Also, if $D$ is total dominating, then irreducible is equivalent to minimal total dominating.

Now let $M$ be minimal dominating and $x\notin M$. Since $M$ dominates $G$, the added vertex $x$ has no $D$-private closed neighbor in $D=M\cup\{x\}$. For $m\in M$, the $D$-private closed neighbors of $m$ are precisely $P_M(m)\setminus N[x]$. Hence conditions (1) and (2) are exactly the irreducibility condition for $M\cup\{x\}$. Moreover, $M\cup\{x\}$ is total iff every isolated vertex of $G[M]$ is adjacent to $x$.

Thus the displayed condition is necessary.

Conversely, suppose $G$ satisfies the displayed condition and let $D$ be irreducible but not minimal dominating. Choose $x\in D$ such that $D\setminus\{x\}$ is dominating. If $D$ is not total, choose an isolated vertex $s\in D$. Since $D$ is irreducible, $x$ is adjacent to some leaf $y$ of $G[D]$. Let $M$ be a minimal dominating subset of $D\setminus\{x\}$. Then $s,y\in M$, and $s$ is still not adjacent to $x$. One checks directly from the irreducibility criterion that $M\cup\{x\}$ is irreducible. This contradicts the displayed condition. Therefore every irreducible non-minimal dominating set is total, hence minimal total dominating. This proves the characterization.

Degenerate cases are included: edgeless graphs satisfy the condition vacuously, and complete graphs satisfy it because every one-vertex extension of a minimal dominating set is total.

Citation: The problem and definitions come from Didem Gözüpek, Ademir Hujdurović, and Martin Milanič, “Characterizations of minimal dominating sets and the well-dominated property in lexicographic product graphs,” Discrete Mathematics & Theoretical Computer Science 19(1), 2017, arXiv:1701.05886. No prior published resolution of Problem 7.1 is used here.