Algebraic distance graphs and rigidity

Homma, M.; Maehara, H.

doi:10.1090/S0002-9947-1990-1012518-X

Algebraic distance graphs and rigidity
HTML articles powered by AMS MathViewer

by M. Homma and H. Maehara PDF

Trans. Amer. Math. Soc. 319 (1990), 561-572 Request permission

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

Norman H. Anning and Paul Erdös, Integral distances, Bull. Amer. Math. Soc. 51 (1945), 598–600. MR 13511, DOI 10.1090/S0002-9904-1945-08407-9
L. Asimow and B. Roth, The rigidity of graphs, Trans. Amer. Math. Soc. 245 (1978), 279–289. MR 511410, DOI 10.1090/S0002-9947-1978-0511410-9
L. Asimow and B. Roth, The rigidity of graphs, Trans. Amer. Math. Soc. 245 (1978), 279–289. MR 511410, DOI 10.1090/S0002-9947-1978-0511410-9
Kiran B. Chilakamarri, Unit-distance graphs in rational $n$-spaces, Discrete Math. 69 (1988), no. 3, 213–218. MR 940076, DOI 10.1016/0012-365X(88)90049-0
Robert Connelly, The rigidity of suspensions, J. Differential Geometry 13 (1978), no. 3, 399–408. MR 551568
R. B. Eggleton, P. Erdős, and D. K. Skilton, Colouring the real line, J. Combin. Theory Ser. B 39 (1985), no. 1, 86–100. MR 805458, DOI 10.1016/0095-8956(85)90039-5
Peter C. Fishburn, On the sphericity and cubicity of graphs, J. Combin. Theory Ser. B 35 (1983), no. 3, 309–318. MR 735198, DOI 10.1016/0095-8956(83)90057-6
P. Frankl and H. Maehara, The Johnson-Lindenstrauss lemma and the sphericity of some graphs, J. Combin. Theory Ser. B 44 (1988), no. 3, 355–362. MR 941443, DOI 10.1016/0095-8956(88)90043-3
Hiroshi Maehara, Note on induced subgraphs of the unit distance graph $E^n$, Discrete Comput. Geom. 4 (1989), no. 1, 15–18. MR 964141, DOI 10.1007/BF02187712
Hiroshi Maehara, Space graphs and sphericity, Discrete Appl. Math. 7 (1984), no. 1, 55–64. MR 722183, DOI 10.1016/0166-218X(84)90113-6
John Milnor, Singular points of complex hypersurfaces, Annals of Mathematics Studies, No. 61, Princeton University Press, Princeton, N.J.; University of Tokyo Press, Tokyo, 1968. MR 0239612
David Mumford, Algebraic geometry. I, Grundlehren der Mathematischen Wissenschaften, No. 221, Springer-Verlag, Berlin-New York, 1976. Complex projective varieties. MR 0453732
B. Roth, Rigid and flexible frameworks, Amer. Math. Monthly 88 (1981), no. 1, 6–21. MR 619413, DOI 10.2307/2320705
Lowell W. Beineke and Robin J. Wilson (eds.), Selected topics in graph theory, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York, 1978. MR 543656
I. R. Shafarevich, Basic algebraic geometry, Die Grundlehren der mathematischen Wissenschaften, Band 213, Springer-Verlag, New York-Heidelberg, 1974. Translated from the Russian by K. A. Hirsch. MR 0366917

Commutative algebra