Sheng Bau, Peter Johnson: Graphs which are intervals, 419-427

Abstract:

A graph $G$ is called an interval if there exist $a, b\in V(G)$ such that $G$ is the union of shortest paths connecting $a$ and $b$. In this paper we show that

1. If $G$ is an interval between $a$ and $b$, then there exists a path $H$ with diameter $d(H) = d(G)$ such that there is a homomorphism $f : G\rightarrow H$ and the distance $\rho (a, b) + 1\leq \vert H\vert\leq \vert G\vert - 1$;
2. Every interval is a connected bipartite graph;
3. If $G$ is an interval between $a$ and $b$ that is not a path, then $G$ has a path $P$ with internal vertices (if any) all of degree $2$ such that deletion of the internal vertices of $P$ from $G$ gives rise to an interval (if $P = uv$ then $G - uv$ is an interval).

Key Words: Diameter, distance, extremal, homomorphism, shortest path.

2020 Mathematics Subject Classification: Primary 05C62; Secondary 05C12.

Download the paper in pdf format here.