TOPICS
Search

Antipodal Graph


Define an antipode of a given graph vertex v_i as a vertex v_j at greatest possible graph distance from v_i. Then an antipodal graph is a connected graph in which each vertex has exactly one antipode (Gorovoy and Zmiaikou 2021).

AntipodalGraphs

The numbers of antipodal graphs on n=1, 2, ... nodes are 1, 1, 0, 2, 1, 5, 8, 73, 660, 9909, ... (OEIS A349635).

Examples of antipodal graphs include Bruhat graphs, cocktail party graphs K_(n×2), even cycle graphs C_(2n) (Gorovoy and Zmiaikou 2021), hypercube graphs Q_n, and path graphs of odd length P_(2n) (Gorovoy and Zmiaikou 2021).

A tree is antipodal iff it has a unique longest path and this path is of odd length (Gorovoy and Zmiaikou 2021).

Every vertex of a geodetic Hamiltonian graph has at least two antipodes (Gorovoy and Zmiaikou 2021).


See also

Antipodal Points, Antipode, Geodetic Graph, Graph Distance Matrix, Longest Path

Explore with Wolfram|Alpha

References

Gorovoy, D. and Zmiaikou, D. "On Graphs with Unique Geoodesics and Antipodes." 19 Nov 2021. https://arxiv.org/abs/2111.09987.Sloane, N. J. A. Sequence A349635 in "The On-Line Encyclopedia of Integer Sequences."

Cite this as:

Weisstein, Eric W. "Antipodal Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/AntipodalGraph.html

Subject classifications