Diameter of 2-distance graphs

NEW

Problem: For finite simple undirected graphs, reconstruct Problem 3.2 as:

Characterize all graphs $G$ with $\operatorname{diam}(G)=2$ such that

where $D_2(G)$ has vertex set $V(G)$, and $uv\in E(D_2(G))$ iff $d_G(u,v)=2$.

Since $\operatorname{diam}(G)=2$, for distinct vertices $u,v$,

so

Result: For $v\in V(G)$, write

the set of vertices nonadjacent to $v$ in $G$.

Then for every graph $G$ with $\operatorname{diam}(G)=2$:

1. $\operatorname{diam}(D_2(G))=2$ iff for every edge $xy\in E(G)$,

2. $\operatorname{diam}(D_2(G))=3$ iff:
   • there exists an edge $xy\in E(G)$ with

• and for every edge $xy\in E(G)$ with $A(x)\cap A(y)=\varnothing$, there exist

 such that

Proof: Let $H=D_2(G)=\overline G$. For an edge $xy\in E(G)$, the vertices $x,y$ are nonadjacent in $H$. Their common neighbors in $H$ are exactly

Thus $d_H(x,y)=2$ iff $A(x)\cap A(y)\neq\varnothing$.

If this holds for every edge $xy\in E(G)$, then every nonadjacent pair in $H$ has a common neighbor, while every nonedge of $G$ is an edge of $H$. Hence $\operatorname{diam}(H)=2$.

If some edge $xy\in E(G)$ has $A(x)\cap A(y)=\varnothing$, then $d_H(x,y)\neq2$. Such a pair has $d_H(x,y)=3$ exactly when there is a path

in $H$, equivalently $a\in A(x)$, $b\in A(y)$, and $ab\notin E(G)$. Therefore all distances in $H$ are at most $3$, and some distance is exactly $3$, precisely under condition (2).

Thus the two stated conditions exactly characterize the cases $\operatorname{diam}(D_2(G))=2$ and $\operatorname{diam}(D_2(G))=3$.

Citation: No external resolution used. The key observation is the definitional identity $D_2(G)=\overline G$ when $\operatorname{diam}(G)=2$.