Antipodal graphs and digraphs
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 di...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
1993-01-01
|
| Series: | International Journal of Mathematics and Mathematical Sciences |
| Subjects: | |
| Online Access: | http://dx.doi.org/10.1155/S0161171293000717 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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. |
|---|---|
| ISSN: | 0161-1712 1687-0425 |