graphs that are intervals

2012-10-09T06:50:29Z

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

Answer by Ben Barber for graphs that are intervals

2012-10-09T08:52:00Z

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

Answer by Aaron Meyerowitz for graphs that are intervals

2012-10-09T17:43:38Z

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.

later

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

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

We thus also have
$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
$d(u,w') \le d(u,u')-1$ as $w' \ne u'.$ Accordingly
$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
$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,
$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.

graphs that are intervals - MathOverflow

graphs that are intervals

Answer by Ben Barber for graphs that are intervals

Answer by Aaron Meyerowitz for graphs that are intervals