definition clarification in graph theory

59 Views Asked by At

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 :)

1

There are 1 best solutions below

1
On BEST ANSWER

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.