What do you call a graph having the property " for every vertex $u$ there exists a vertex $v$ suchthat $G=I(u,v)$
9
-
$\begingroup$ What does $I(u, v)$ mean? $\endgroup$– Qiaochu YuanCommented Oct 9, 2012 at 6:55
-
$\begingroup$ $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$) $\endgroup$– ramCommented Oct 9, 2012 at 6:59
-
$\begingroup$ 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)$. $\endgroup$– OlivierCommented Oct 9, 2012 at 7:58
-
$\begingroup$ Oliver you are wrong. Even cycles should satisfy the condition. For a vertex u pick the opposite vertex. $\endgroup$– PatrikCommented Oct 9, 2012 at 8:08
-
$\begingroup$ what about even cycles $\endgroup$– ramCommented Oct 9, 2012 at 8:09
|
Show 4 more comments
2 Answers
$\begingroup$
$\endgroup$
2
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.
answered Oct 9, 2012 at 17:43
-
1$\begingroup$ $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. $\endgroup$ Commented Oct 10, 2012 at 7:46
-
$\begingroup$ 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. $\endgroup$ Commented Oct 10, 2012 at 18:11
$\begingroup$
$\endgroup$
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".
answered Oct 9, 2012 at 8:52