MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 4 down vote accepted

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.

share|cite|improve this answer
Thank you, Jukka. I will try thinking along these lines. – gphilip Aug 30 '10 at 2:31

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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