Antipodal graphs and digraphs

Abstract

The antipodal graph of a graph G, denoted by A(G), has the same vertex set as G with an edge joining vertices u and v if d(u,v) is equal to the diameter of G. (If G is disconnected, then diam G=∞.) This definition is extended to a digraph D where the arc (u,v) is included in A(D) if d(u,v) is the diameter of D. It is shown that a digraph D is an antipodal digraph if and only if D is the antipodal digraph of its complement. This generalizes a known characterization for antipodal graphs and provides an improved proof. Examples and properties of antipodal digraphs are given. A digraph D is self-antipodal if A(D) is isomorphic to D. Several characteristics of a self-antipodal digraph D are given including sharp upper and lower bounds on the size of D. Similar results are given for self-antipodal graphs.

Keywords

• antipodal graphs
• antipodal digraphs.