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
    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?2012-11-22
  • 0
    Yes, but which vertices $u,v$ in $G$ satisfy $d(u,v)\le d$ if $d$ is the diameter of $G$ (see definition above)?2012-11-22
  • 0
    The ones which have the distance lower than the diameter?2012-11-22
  • 0
    Which ones are those? Are there any that have distance greater than the diameter? Recall that the diameter is the greatest distance between vertices.2012-11-22
  • 0
    Well the definition says the adjacent but maybe for the diameter it's the opposite.. And yeah there isn't anything greater than the diameter, radius is smaller..2012-11-22
  • 0
    Well if there are no $u,v$ whose distance is greater than the diameter, then every $u,v$ have distance less than or equal to the diameter, so every $u,v$ are adjacent in $G^d$. So if you have a graph with $n$ vertices and every pair is adjacent, what do you call that graph?2012-11-22
  • 0
    A complete graph? $K_n$ ?2012-11-22
  • 0
    Bingo! That's the answer.2012-11-22
  • 0
    Haha okay so to be straight, $G^d$ is the complete graph whose set of nodes is $V$ and where verttices $u$ and $v$ are adjacent if and only if $d(u,v)<=d$ in $G$, knowing that every pair is adjacent and the distance is less or equal to the diameter?2012-11-22
  • 0
    let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/6494/discussion-between-rayradjr-and-max-bummer)2012-11-22