MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What do you call a graph having the property " for every vertex $u$ there exists a vertex $v$ suchthat $G=I(u,v)$

share|cite|improve this question
What does $I(u, v)$ mean? – Qiaochu Yuan Oct 9 '12 at 6:55
$I(u,v)$ means the interval ie, the set of all vertices which lie in some shortest path between $u$ and $v$(inclusive of $u$ and $v$) – ram Oct 9 '12 at 6:59
I think I call such a graph an edge. Indeed, if $G$ has more than three vertices, let $u,v$ be as in the definition (so a shortest path $P$ between $u$ and $v$ covers $G$), let $w$ be a distinct vertex and let $z$ be any vertex. Then $w$ and $z$ are both on $P$ so following $P$ from $w$ to $z$ yields a path strictly smaller than $P$ so the shortest path from $w$ to $z$ cannot cover $G$. So there is no $z$ such that $G=I(w,z)$. – Olivier Oct 9 '12 at 7:58
Oliver you are wrong. Even cycles should satisfy the condition. For a vertex u pick the opposite vertex. – Patrik Oct 9 '12 at 8:08
what about even cycles – ram Oct 9 '12 at 8:09

What do you know about graphs with this property? I don't know any terminology which would be widely recognized. There is much terminology which can be utilized. to create a name.

A graph with this property has for each $u$ a unique $u'$ such that $G=I(u,u')$ so $u$ and $u'$ might be considered antipodal or polar. I will show below that $d(u,u')=d(v,v')$ for any pair which does make $G$ an Antipodal Graph if it is imprimitive and distance regular. However we do not know if it is regular or distance regular. Polar graph suggests polar graph paper.

A geodesic from $u$ to $v$ is a shortest path. I liked geodesic graph. I was excited to discover the notion of the geodetic number of a graph and thought yours could be called 2-geodetic. But that is not quite it.

If there is one $u$ with this property and the graph is distance regular then every vertex has this property. Of course a graph with a vertex transitive automorphism group is distance regular. I wonder if a graph with your property has to be regular. I doubt it but don't see an easy counter-example (yet).

The longest geodesic involving $u$ is the eccentricity of $u.$ The diameter and radius are the maximum and minimum eccentricity in a graph. I wonder if every vertex has the same eccentricity in a graph with your property. If so then radius=diameter and every vertex is both central and extreme in that it has eccentricity equal to the radius and is the end of a diameter. diametric graph has another meaning.


This seems like an interesting concept, which raises the chances that it must be discussed (and named) somewhere. Let $u'$ be the unique vertex at maximum distance from $u$ so $u=u''$ and

  1. For any $u,y$, $d(y,u')=d(u,u')-d(u,y).$

    We thus also have

  2. $d(u',y)=d(y',y)-d(y',u').$

    We may assume $d(u,u') \gt 1.$ I claim that $u \to u'$ is actually an automorphism of $G:$ Let $d(u,w)=1.$ Then

  3. $d(u,w') \le d(u,u')-1$ as $w' \ne u'.$ Accordingly
  4. $d(w,w') = d(w,u)+d(u,w') \le d(u,u').$

    By the same reasoning, $d(u,u') \le d(w,w').$ So

  5. $d(u,u')=d(v,v')$ for any $u,v.$

    To justify the claim that $u \to u'$ is an automorphism we will show that in general,

  6. $d(a,b)=d(b',a')$ which then implies $d(u,w)=1$ iff $d(u',w')=1.$

Using 2) twice we have $d(a,b)=d(b',b)-d(b',a)$ and $d(b',a')=d(a,a')-d(a,b')$ but $d(b',b)=d(a,a')$ and $d(b',a)=d(a,b')$.

Thus we always have $deg(u)=deg(u')$ although I am not sure about $deg(u)=deg(v)$

If we identify all pairs of vertices $u,u',$ we get a graph $H$ with half as many vertices. I wonder if $g$ has to be bipartite.

share|cite|improve this answer
$G$ is not necessarily bipartite, nor is it necessarily regular. Take a cube in at least 3 dimensions, and add new vertices in the centres of a pair of opposite (square) faces. Then $G$ inherits the property from the cube, as any path that goes round two edges of a square can be re-routed to go through the new point (and the two new points are antipodal). This property is also preserved under taking Cartesian products, so any classification has got to cope with someone coming along and taking the product of all your graphs with the dodecahedron. – Ben Barber Oct 10 '12 at 7:46
Good point. For a square one can add an extra point to each of the "opposite faces" to get an octahedron which is regular but, like a dodecahedron or icosohedron is not bipartite. – Aaron Meyerowitz Oct 10 '12 at 18:11

The least $k$ such that the vertices of $G$ can be covered by intervals $I(u_i,u_j)$, $1\leq i < j \leq k$, has been called the geo-number of $G$. Given any vertex $u$, you can obtain a (not necessarily smallest possible) covering set by taking $u$ and all of the vertices at locally-maximal distance from $u$; if the number of elements in this set is equal to the geo-number then $u$ is a geo-vertex. So you could call them "graphs with geo-number 2 with every vertex a geo-vertex".

A.P. Santhakumaran and P. Titus, "The Geo-Number Of A Graph", pp. 65-78, Ars Combinatoria CVI, July 2012

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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