0
$\begingroup$

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.

1 Answers 1

1

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$.

Graphs of <span class=P_8^2 and $P_8^3$.">

  • 0
    let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/6494/discussion-between-rayradjr-and-max-bummer)2012-11-22