Take the 2-minute tour ×
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.

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|improve this question
    
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

1 Answer 1

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