DIMACS TR: 2001-46

Antipodal graphs of small diameter

Authors: Dragan Stevanovic


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