Not all partial cubes are $\Theta$-graceful

Nathann Cohen, Matjaž Kovše

It is shown that the graph obtained by merging two vertices of two 4-cycles is not a $\Theta$-graceful partial cube, thus answering in the negative a question by Brešar and Klavžar from…