Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 

 

Algebraic distance graphs and rigidity


Authors: M. Homma and H. Maehara
Journal: Trans. Amer. Math. Soc. 319 (1990), 561-572
MSC: Primary 52C25; Secondary 05C12, 05C75
DOI: https://doi.org/10.1090/S0002-9947-1990-1012518-X
MathSciNet review: 1012518
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: An algebraic distance graph is defined to be a graph with vertices in $ {E^n}$ in which two vertices are adjacent if and only if the distance between them is an algebraic number. It is proved that an algebraic distance graph with finite vertex set is complete if and only if the graph is "rigid". Applying this result, we prove that (1) if all the sides of a convex polygon $ \Gamma $ which is inscribed in a circle are algebraic numbers, then the circumradius and all diagonals of $ \Gamma $ are also algebraic numbers, (2) the chromatic number of the algebraic distance graph on a circle of radius $ r$ is $ \infty $ or $ 2$ accordingly as $ r$ is algebraic or not. We also prove that for any $ n > 0$, there exists a graph $ G$ which cannot be represented as an algebraic distance graph in $ {E^n}$.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 52C25, 05C12, 05C75

Retrieve articles in all journals with MSC: 52C25, 05C12, 05C75


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1990-1012518-X
Article copyright: © Copyright 1990 American Mathematical Society