2
$\begingroup$

I was studying about Almost Self-Centered Graphs (ASC). ASC graphs are introduced as the graphs with exactly two non-central vertices. Of course, the remaining two vertices are diametrical. My doubt is that if we have two non-central vertices x and y, does it mean that d(x,y) = ecc(x) = ecc(y). I am quite confused. Tried few examples and I found it to be true. If I am wrong please rectify me. thanks a lot for help :)

$\endgroup$
2
$\begingroup$

This is true.

Suppose $r$ is the radius of the graph. Then any vertex except for $x$ and $y$ has eccentricity $r$, and $x$ and $y$ have eccentricity greater than $r$.

There must be some vertex $z$ with distance $d(x,z) = \operatorname{ecc}(x)$, by the definition of eccentricity. However, $z$ must in fact be $y$, because, were $z$ not $y$, $\operatorname{ecc}(z) < \operatorname{ecc}(x) = d(x,z)$, a contradiction. Therefore, $d(x,y) = \operatorname{ecc}(x)$.

The same logic holds for $y$, proving the theorem.

$\endgroup$
  • $\begingroup$ thanks a lot for nice explanation :) $\endgroup$ – monalisa Nov 19 '13 at 4:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.