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$

1 Answer 1

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
  • 1
    $\begingroup$ Brilliant, and thanks for the nice visualization! $\endgroup$ Jan 28, 2019 at 12:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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