# Graphs of different orders( at different powers)

Given a connected graph $G =(V,E)$ and a positive integer $k$, the k-th power of $G$, denoted $G^k$ , is the graph whose set of nodes is $V$ and where vertices $u$ and $v$ are adjacent in $G_k$ if and only if $d(u,v) \le k$ in $G$.

$P_8$ is a path graph with 8 vertices such as: o-o-o-o-o-o-o-o

$C_{10}$ is a cycle graph: $C_{10}$ has 10 vertices.

$d(u,v)$ is the distance between $u$ and $v$, which is the length of the shortest path $u-v$ from $u$ to $v$ in graph $G$.

I know that two vertices are adjacent in the 2nd power if and only if there's a path of length at most 2 between them in $P_8$.

• Draw the 2-nd and 3-rd powers of $P_8$ and $C_{10}$ .
• For a graph $G$ of order $n$, what is $G^{diam(G)}$

I know the stuff above and I am asking for any answers and help, appreciate it.

-
I think this should be tagged as a homework –  Amr Nov 22 '12 at 20:32
@Amr, homework or not, what do you say about my comment on the answer? Is this what I'm supposed to find? –  Max Bummer Nov 22 '12 at 21:37

I'll give you the graphs of $P_8^2$ and $P_8^3$, and hopefully this will help you figure out $C_{10}^2$ and $C_{10}^3$. As for the diameter problem, recall that the diameter is the least non-negative integer $d$ such that $d(u,v)\le d$ for all $u,v\in V$. Knowing this and the definition of $G^k$, can you figure out what $G^d$ is?
Here are $P_8^2$ and $P_8^3$.
I figured out the circular ones, thank you. Regarding the second thing -- Given a graph G=(V,E), $G^d$ is the graph whose set of nodes is V and where vertices u and v are adjacent if and only if $d(u,v)<=d$ in $G$. Is this what $G^d$ is? –  Max Bummer Nov 22 '12 at 21:34
Yes, but which vertices $u,v$ in $G$ satisfy $d(u,v)\le d$ if $d$ is the diameter of $G$ (see definition above)? –  rayradjr Nov 22 '12 at 21:44