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.

I am trying to work out a problem. Given a self-centered graph, is the square of the graph also a self-centered graph? I tried numerically on few graphs given in http://www.matf.bg.ac.rs/~zstanic/indexdiam.html and I got the result that, yes, they are still self-centered. But I am not getting any idea to prove it theoretically.

A self-centered graph is a graph whose diameter equals its radius. Or where the eccentricity of every vertex is the same.

The $k$th power of a graph $G$ is a graph with the same set of vertices as $G$ and an edge between two vertices iff there is a path of length at most $k$ between them.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

Since the square of the graph will add edges between every pair of vertices a distance 2 apart, you should be able to see that if the distance between two vertices in $G$ is $2k$ for some integer $k$ then the distance in $G^2$ will be $k$. What happens for vertices an odd distance apart?

Now in your self-centered graph we know that for every vertex there exists at least one vertex at the given distance, and so in the square of your graph the eccentricities will all decrease by the same amount. Thus the square is self-centered too.

Added extra detail: Suppose $u$ and $w$ are a distance $d$ apart in $G$. Then in $G^2$, they will be a distance $\lceil \frac{d}{2} \rceil$ apart. If the path was $u v_1 v_2 v_3 v_4 \ldots w$ in $G$ then there will exist a path in $G^2$ which skips every other vertex: $u v_2 v_4 \ldots w$. If a path of length less than $\frac{d}{2}$ exists in $G^2$ between $u$ and $w$ then we can conclude that in $G$ there was a path between them of length less than $d$, a contradiction.

share|improve this answer
    
Can u please clarify your second para "Now in your self-centered graph we know that for every vertex there exists at least one vertex at the given distance, and so in the square of your graph the eccentricities will all decrease by the same amount". is that a known result? kindly help. i am unable to get it. –  monalisa Mar 7 '13 at 5:48
    
how's that @monalisa? –  jp26 Mar 9 '13 at 13:52
    
thanks a ton .... now its very much clear to me... –  monalisa Mar 10 '13 at 13:34

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.