What is known about the $k^{\mathrm{th}}$ powers of graphs of diameter $k+1$?

Question

Let $G$ be a simple unweighted graph. The distance between two vertices $u,v$ in $G$ is the length of a shortest path in $G$ between $u$ and $v$. The diameter of $G$, denoted $diam(G)$, is the largest distance between two vertices in $G$. For a natural number $k$, The $k^{\mathrm{th}}$ power of $G$, denoted $G^{k}$, is the graph obtained from $G$ by adding edges between every two vertices $u,v$ where the distance between $u,v$ in $G$ is at most $k$.

Let $\mathcal{F}_{k}$ be the family of all graphs that are the $k^{\mathrm{th}}$ powers of graphs of diameter $k+1$. That is,

$\mathcal{F}_{k} = \{G^{k}\mid diam(G)=k+1\}$

$\mathcal{F}_{1}$ is the set of all graphs of diameter $2$, and for all $k\ge2$, $\mathcal{F}_{k}\subseteq\mathcal{F}_{2}$.

Is something more known about the structure of the graphs in $\mathcal{F}_{k}$ for $k\ge2$? In particular, are these containments strict? Do we get more structure the higher the value of $k$?

Thanks for any ideas, pointers, and/or references on this.

Answer 1

The containments must be strict for the trivial reason that each $\mathcal F_k$ contains a graph with $k+2$ nodes (the case $G$ = path) but no graph with $k+1$ nodes (if $G$ has diameter $k+1$, it must have at least $k+2$ nodes).

For further insight into the structure of $\mathcal F_k$, I'd study the structure of the complements of the graphs in $\mathcal F_k$. Each edge in the complement of $G^k$ corresponds to a diameter of $G$; that is, if you have an edge $\{u,v\}$ in the complement of $G^k$, the distance between $u$ and $v$ is exactly $k+1$ in $G$. Thus your question is really about the structure of the diameters of graphs.