## DIMACS TR: 2001-46

## Antipodal graphs of small diameter

### Authors: Dragan Stevanovic

**
ABSTRACT
**

A proper metric space $X=(X,d)$ is called {\em antipodal}
if -- with $[x,y]=\{z\in X\,\colon\,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 {\em 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$.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-46.ps.gz

DIMACS Home Page