1
$\begingroup$

Let $G=(V,E)$ be a finite, simple, undirected graph. Let $D_2(G)$ be the graph with vertex set $V$, and two vertices form an edge if and only if they have distance $2$ in the original graph $G$.

Note that, if $C_{2k+1}$ is the circle on $2k+1$ points for an integer $k\geq 2$, we have $C_{2k+1}\cong D_2(C_{2k+1})$.

Question. Is there a connected, non-regular graph $G=(V,E)$ with $|V|>2$ such that $G\cong D_2(G)$?

$\endgroup$
8
$\begingroup$

Yes, the hexagon ABCDEF with the additional edge of AC has this property. The first graph shows $G$ and the others show two views of $D_2(G)$.

G D_2(G) showing D_2 D_2(G) showing iso

(Graphs courtesy of NCTM)

$\endgroup$
  • 1
    $\begingroup$ Brilliant, and thanks for the nice visualization! $\endgroup$ – Dominic van der Zypen Jan 28 at 12:10

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.