Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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.

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

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 $P_8^2$ and $P_8^3$.

share|cite|improve this answer
    
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
    
The ones which have the distance lower than the diameter? – Max Bummer Nov 22 '12 at 21:50
    
Which ones are those? Are there any that have distance greater than the diameter? Recall that the diameter is the greatest distance between vertices. – rayradjr Nov 22 '12 at 21:52
    
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.. – Max Bummer Nov 22 '12 at 21:55

Your Answer

 
discard

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.