Antipodal graphs and oriented matroids

✍ Scribed by Komei Fukuda; Keiichi Handa

• Publisher: Elsevier Science
• Year: 1993
• Tongue: English
• Weight: 786 KB
• Volume: 111
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(93)90159-q

✦ Synopsis

A graph is antipodal if, for every vertex c', there exists exactly one vertex V which is not closer to r than every vertex adjacent to 6. In this paper we consider the problem of characterizing tope graphs of oriented matroids, which constitute a broad class of antipodal graphs. One of the results is to characterize tope graphs of more general systems than oriented matroid, namely, an L'-embeddable system and acycloid. Another is to characterize tope graphs of oriented matroids of rank at most three. The characterization theorem says: a graph G is isomorphic to the tope graph of an oriented matroid of rank at most three if and only if G is antipodal, planar and isometrically embeddable in some hypercube.

For tope graphs of oriented matroids of any higher rank, the characterization problem is still open.

vertex graph K1 to be antipodal and symmetric-even.