×

Antipodal graphs and oriented matroids. (English) Zbl 0782.05069

Summary: A graph is antipodal if, for every vertex \(v\), there exists exactly one vertex \(\bar v\) which is not closer to \(v\) than every vertex adjacent to \(\bar v\). 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 matroids, namely, an \(L^ 1\)-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.

MSC:

05C75 Structural characterization of families of graphs
05B35 Combinatorial aspects of matroids and geometric lattices
05C10 Planar graphs; geometric and topological aspects of graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Avis, D., Hypermetric spaces and the Hamming cone, Canad. J. Math., 33, 795-802 (1981) · Zbl 0445.52008
[2] Berman, A.; Kotzig, A., Cross-clonning and antipodal graphs, Discrete Math., 69, 107-114 (1988) · Zbl 0667.05048
[3] Blake, I. F.; Gilchrist, J. H., Addresses for graphs, IEEE Trans. Inform. Theory, 19, 683-688 (1973) · Zbl 0267.94044
[4] Bland, R.; Las Vergnas, M., Orientability of matroids, J. Combin. Theory Ser. B, 24, 94-123 (1978) · Zbl 0374.05016
[5] Cordovil, R., Oriented matroids of rank three and arrangements of pseudolines, Ann. Discrete Math., 17, 219-223 (1983) · Zbl 0521.05023
[6] Djoković, D.Ž., Distance-preserving subgraphs of hypercubes, J. Combin. Theory Ser. B, 14, 263-267 (1973) · Zbl 0245.05113
[7] Edelman, P. H., A partial order on the regions on \(R^n\) dissected by hyperplanes, Trans. Amer. Math. Soc., 280, 617-631 (1984) · Zbl 0555.06003
[8] Edelsbrunner, H., Algorithms in Combinatorial Geometry (1987), Springer: Springer Berlin · Zbl 0634.52001
[9] Folkman, J.; Lawrence, J., Oriented matroids, J. Combin. Theory Ser. B, 25, 199-236 (1978) · Zbl 0325.05019
[10] Fukuda, K., Oriented matroid programming, (Ph. D. Thesis (1982), University of Waterloo)
[11] Fukuda, K.; Handa, K., Perturbation of oriented matroids and acycloids, (Research Report B-172 (1985), Department of Information Sciences, Tokyo Institute of Technology)
[12] Fukuda, K.; Saito, S.; Tamura, A., Combinatorial face enumeration in arrangements and oriented matroids, Discrete Appl. Math., 31, 141-149 (1991) · Zbl 0752.05016
[13] Glivjak, F.; Kotzig, A.; Plesnik, J., Remark on the graphs with a central symmetry, Monatsh. Math., 74, 302-307 (1970) · Zbl 0202.55701
[14] Göbel, F.; Veldman, H. J., Even graphs, J. Graph Theory, 10, 225-239 (1986) · Zbl 0593.05055
[15] Handa, K., The faces and coboundaries of an acycloid, (Topology and Computer Science (1987), Kinokuniya), 535-545
[16] Handa, K., A characterization of oriented matroids in terms of topes, European J. Combin., 11, 41-45 (1990) · Zbl 0748.05042
[17] Harary, F.; Hayes, J. P.; Wu, H.-J., A survey of the theory of hypercube graphs, Comput. Math. Appl., 15, 277-289 (1988) · Zbl 0645.05061
[18] Mandel, A., Topology of oriented matroids, (Ph. D. Thesis (1982), University of Waterloo)
[19] Mulder, M., The structure of median graphs, Discrete Math., 24, 197-204 (1978) · Zbl 0394.05038
[20] Sabidussi, G., The structure of antipodal graphs, Resumes/Abstracts (1990), Theorie des graphes et combinatoire, 4ème Colloque International, Marseille
[21] Tomizawa, N., Theory of acycloid and holometry, Graph Theory and Applications, 534, 91-138 (1984), (in Japanese)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.