3
$\begingroup$

Let $(G,E)$ be a finite undirected graph, and $d$ be the usual shortest path distance on $G$. The graph is not necessary connected, so $d(v',v'') = \infty$ if there are no paths from $v$ to $v'$. For $A\subseteq G$ we put $ d(v,A) = \min\limits_{u\in A}d(v,u). $ My question is the following: let us define for $A\subseteq G$ $ m(A) = \max\limits_{v\in A}d(v,G\setminus A). $ Is there a name for $m(A)$, maybe you can give a reference on this?

1 Answers 1

1

I've not found a specific term for what you're looking for, but it seems similar to Eccentricity.

The eccentricity $\epsilon(v)$ of a graph vertex $v$ in a connected graph $G$ is the maximum graph distance between $v$ and any vertex $u$ of $G\backslash \{v\}$.

If you define the graph distance between a set and a vertex as you did above: $d(v,A) = \min\limits_{u\in A}d(v,u)$, then you could generalise this definition to vertex sets:

The eccentricity $\epsilon(A)$ of a set of graph vertices $A$ in a connected graph $G$ is the maximum graph distance between $A$ and any vertex $u$ of $G\backslash A$.

i.e. $\epsilon(A) = \max\limits_{u \in G \backslash A} d(u,A)$

So strictly speaking, $\epsilon(G \backslash A) = \max\limits_{u \in A} d(u,G \backslash A)$, which looks like what you asked for.

Not quite an answer, but hopefully it'll help in some way.

  • 0
    Thank you for the answer, an interesting observation. I thought about the connections between $m(A)$ and the eccentricity, but mostly focused on the radius of $A$ which in the end doesn't seem to be connected anyhow to $m(A)$2012-05-10