3
$\begingroup$

On the Wikepdia Page Graph Center I saw that the center of graph is the set of vertices with minimal eccentricity, i.e the set of vertices, whose maximal distance to other vertices is minimal.
On the website the term "eccentricity" links to Distance (Graph Theory).

Now, as eccentricity is, to my knowledge, in 2D geometry exclusively used as a property of ellipses and hyperbolas, I wonder how it should be related to sets.

The problem I have with the use of the term eccentricity for denoting a set of things is twofold: firstly, eccentricity is a numeric value in classical geometry and secondly, I wanted to use the term eccentricity in the classical sense to define a generalization of ellipses to complete graphs, which now seems not possible anymore because the "eccentricity claim" has already been staked.

Questions:

  • is the use of the term eccentricity in the definition of a graph's center customary in graph theory and if yes,
    • who first used it to define graph centers
    • what was the motiviation/justification for using eccentricity in that definition
$\endgroup$
4
$\begingroup$

Re: 'is it customary'. Yes, this is the customary term, and I don't know any reasonable alternative to using the eccentricity function. The term (with exactly this definition) already occurs on page 35 of the slim yet influential textbook

[H1969] Frank Harary, Graph Theory, Addison Wesley Publishing Company, First Edition, 1969

Re "who first used it to define graph centers": needless to say, this cannot be known, but again it is at least as old as [H1969, p. 35], where one reads

"The *eccentricity $e(v)$ of a point $v$ in a connected graph $G$ is $\max d(u,v)$ for all $u$ in $G$. The radius $r(G)$ is the minimum eccentricity of the points. Note that the maximum eccentricity is the diameter. A point $v$ is a central point if $e(G)=r(G)$, and the center of $G$ is the set of all central points.

[bold emphasis added]

Re "what was the motiviation/justification for using eccentricity in that definition": this can only be guessed or answered by authors like Harary themselves. That said, a reasonable just-so-story is this: consider the definition 'center=set of vertices whose eccentricity equals the graph's radius', and then note that in the most paradigmatic shape having a 'center', i.e, the humble circle, the definition makes perfect sense: for any point $p$ in a circle define its 'eccentricity' to be the Euclidean length of the segment from $p$ through the circle's centre $c$ to the circle's circumference; then the one-element set $\{c\}$ equals the set of all points of the circle whose eccentricity equals the radius. The story goes that the early graph theorists were wont to scrawl with pens on paper, and often these shapes were circular, and this gave them ideas.

In that regard, let me close with a warning: the 'center' thus defined does not alway look quite so intuitively 'central'; e.g. in the graph represented by

enter image description here [graph and caption by present author]

each and every vertex is central (with eccentricity 2), and yet the automorphism group of the graph acts on the vertex set with a whopping four distinct orbits $\{0\}$, $\{3\}$, $\{1,2\}$, $\{4,5\}$. (In other words, whereas all vertices are being lumped together into the same 'eccentricity-class', there exist quite distinct-looking vertices, and there are four types of vertices.)

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thanks for the detailed explanation and opinion(?) on the matter. I will then avoid using the term eccentricity explicitly when defining the generalization of smallest enclosing ellipse to connected graphs. $\endgroup$ – Manfred Weis Feb 25 '18 at 11:31
  • $\begingroup$ Of course, regarding the term 'eccentricity of a conic section', in particular, 'eccentricity of an ellipse': I think there is no connection between that and 'eccentricity of a vertex'. $\endgroup$ – Peter Heinig Feb 25 '18 at 12:04
  • $\begingroup$ I don't see "opinion" as something negative in general; if it relates to arguments that are based on experience and is not related to insisting on knowing the one and only truth without being able to provide proofs, then I appreciate opinions as ideas for further investigation or possible explanations. When I used the term "opinion" in my comment, it was in the positive sense and not in the stigmatized sense. $\endgroup$ – Manfred Weis Feb 25 '18 at 12:41

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.