graphs that are intervals - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T20:41:39Z http://mathoverflow.net/feeds/question/109204 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/109204/graphs-that-are-intervals graphs that are intervals ram 2012-10-09T06:50:29Z 2012-10-10T04:41:29Z <p>What do you call a graph having the property " for every vertex $u$ there exists a vertex $v$ suchthat $G=I(u,v)$</p> http://mathoverflow.net/questions/109204/graphs-that-are-intervals/109209#109209 Answer by Ben Barber for graphs that are intervals Ben Barber 2012-10-09T08:52:00Z 2012-10-09T08:52:00Z <p>The least $k$ such that the vertices of $G$ can be covered by intervals $I(u_i,u_j)$, $1\leq i &lt; j \leq k$, has been called the <em>geo-number</em> 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 <em>geo-vertex</em>. So you <em>could</em> call them "graphs with geo-number 2 with every vertex a geo-vertex".</p> <p><a href="http://www.combinatorialmath.ca/arscombinatoria/vol106.html" rel="nofollow">A.P. Santhakumaran and P. Titus, "The Geo-Number Of A Graph", pp. 65-78, Ars Combinatoria CVI, July 2012</a></p> http://mathoverflow.net/questions/109204/graphs-that-are-intervals/109244#109244 Answer by Aaron Meyerowitz for graphs that are intervals Aaron Meyerowitz 2012-10-09T17:43:38Z 2012-10-10T04:41:29Z <p>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. </p> <p>A graph with this property has for each $u$ a <em>unique</em> $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 <strong>Antipodal Graph</strong> <em>if</em> it is imprimitive and distance regular. However we do not know if it is regular or distance regular. <em>Polar graph</em> suggests polar graph paper.</p> <p>A <em>geodesic</em> from $u$ to $v$ is a shortest path. I liked <strong>geodesic graph.</strong> I was excited to discover the notion of the <strong><a href="http://www.mat.utfsm.cl/scientia/archivos/vol20/vol20art11.pdf" rel="nofollow">geodetic number</a></strong> of a graph and thought yours could be called <strong>2-geodetic.</strong> But that is not quite it. </p> <p>If there is one $u$ with this property and the graph is <a href="http://en.wikipedia.org/wiki/Distance-regular_graph" rel="nofollow">distance regular</a> 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).</p> <p>The longest geodesic involving $u$ is the <em>eccentricity</em> 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. <strong>diametric graph</strong> has another meaning.</p> <p><strong>later</strong> </p> <p>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</p> <ol> <li><p>For any $u,y$, $d(y,u')=d(u,u')-d(u,y).$ </p> <p>We thus also have </p></li> <li><p>$d(u',y)=d(y',y)-d(y',u').$ </p> <p>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 </p></li> <li>$d(u,w') \le d(u,u')-1$ as $w' \ne u'.$ Accordingly</li> <li><p>$d(w,w') = d(w,u)+d(u,w') \le d(u,u').$ </p> <p>By the same reasoning, $d(u,u') \le d(w,w').$ So </p></li> <li><p>$d(u,u')=d(v,v')$ for any $u,v.$ </p> <p>To justify the claim that $u \to u'$ is an automorphism we will show that in general,</p></li> <li>$d(a,b)=d(b',a')$ which then implies $d(u,w)=1$ iff $d(u',w')=1.$</li> </ol> <p>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')$.</p> <p>Thus we always have $deg(u)=deg(u')$ although I am not sure about $deg(u)=deg(v)$</p> <p>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.</p>