For a given graph $G = (V, E)$, construct a graph $G' = (V', E')$ where
- $V' = V \uplus V$ (disjoint union)
- $( (b, v), (d, u) ) \in E'$ (with $b,d\in \mathbb B$) iff $(v,u)\in E$ and either $b = d$ or $v\neq u$
Essentially, it is the union of the graph products $G\,\Box\, (0\;\;1)$ and $G\times (0{-}1)$. Two copies of $G$ with every pair of vertices connected according to $G$'s layout, excepting a direct connection between any pair of vertices.
I'm looking to use it to define boolean satisfiability probles in terms of tolerance relations/dependency graphs, so each vertex of $G$ represents a variable and each vertex of $G'$ represents assigning a variable to 0 or 1.
ETA: $\mathbb B = \{0, 1\}$, the boolean domain. Used in the definition of disjoint union: $A\uplus B = A\times \{0\} \cup B\times \{1\} \subseteq (A\cup B)\times \mathbb B$.
A partial answer I have arrived at is to perform what is in the litterature known as “vertex cleaving” on every vertex.