Tuesday 11 September 2007

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

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 $kge2$, $mathcal{F}_{k}subseteqmathcal{F}_{2}$.



Is something more known about the structure of the graphs in $mathcal{F}_{k}$ for $kge2$? 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.

No comments:

Post a Comment