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)$?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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)

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .