Antipodal graphs of small diameter


Dragan Stevanović




A proper metric space $X=(X,d)$ is called \emph{antipodal} if---with $[x,y]=\{z\in X:d(x,y)=d(x,z)+d(z,y)\}$---for every $x\in X$ there exists some $y\in X$ such that $[x,y]=X$. A connected undirected finite graph $G$ is called \emph{antipodal} if its associated graph metric is antipodal. Here we characterize antipodal graphs of diameter 3 and show that almost every graph is an induced subgraph of some antipodal graph of diameter 3.