2
$\begingroup$

I want to know how to calculate the eccentricity of a vertex in
a weighted graph, I know that when ever we talk about weighted graph if we want
to calculate any distance we consider the weights instead of the number of edges, but in the case of the eccentricity all the articles I found on the
internet never mentioned the case of weighted graph.

$\endgroup$
0
$\begingroup$

The usual definition of eccentricity of a vertex $v$ in an unweighted graph $G$ is the maximum over all distance from $v$ to vertices $w\in G$. You can use literally exactly the same definition for a weighted graph.

More explicitly, for a connected undirected weighted graph $G=(V,E,w)$ where $w:E\to \mathbb R^{\geq 0}$ is a weight function, define the distance between vertices $v,w$ to be $$d_G(v,w)=\min_P \sum_{e\in P}w(e) $$ where the minimum is over all paths $P$ connecting $v$ and $w$.

Now define the eccentricity of a vertex $v$ as $$e_G(v)=\max_w d_G(v,w).$$

Not sure how widespread the use of this definition is but it seems to be a pretty natural generalization.

$\endgroup$

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.