Abstract
We extend recent results of Abdo Alfakih, who constructed Colin de Verdière matrices for complements of penny graphs from Euclidean distance matrices, by interpreting them using the sphere representations of Kotlov, Lovász, and Vempala. Our results apply to complements of contact graphs of unit spheres in arbitrary dimension.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alfakih, Abdo, Y.: On the Colin de Verdière graph number and penny graphs. arXiv:2006.05197
de Verdière, C.: Yves, Sur un nouvel invariant des graphes et un critère de planarité, (French). J. Combin. Theory Ser. B 50(1), 11–21 (1990). https://doi.org/10.1016/0095-8956(90)90093-F
Diestel, R.: Graph theory, 5th ed., Graduate Texts in Mathematics, vol. 173, Springer, Berlin. (2017). https://doi.org/10.1007/978-3-662-53622-3
Gower, J.C.: Euclidean distance geometry. Math. Sci. 7(1), 1–14 (1982)
Gower, J.C.: Properties of Euclidean and non-Euclidean distance matrices. Linear Algebra Appl. 67, 81–97 (1985). https://doi.org/10.1016/0024-3795(85)90187-9
Hogben, L.: Nordhaus-Gaddum problems for Colin de Verdière type parameters, variants of tree-width, and related parameters, Recent trends in combinatorics, IMA Vol. Math. Appl., 159, Springer, [Cham], 275–294 (2016). https://doi.org/10.1007/978-3-319-24298-9_12
Horn, R.A., Johnson, C.R.: Matrix Analysis, 2nd edn. Cambridge University Press, Cambridge (2013)
Kotlov, A., László, L., Vempala, S.: The Colin de Verdière number and sphere representations of a graph. Combinatorica 17(4), 483–521 (1997). https://doi.org/10.1007/BF01195002
László, L.: Graphs and geometry, American Mathematical Society Colloquium Publications, 65, American Mathematical Society, Providence, RI, (2019), https://doi.org/10.1090/coll/065
Lovász, L., Schrijver, A.: A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs. Proc. Am. Math. Soc. 126(5), 1275–1285 (1998). https://doi.org/10.1090/S0002-9939-98-04244-0
Neumaier, A.: Distance matrices, dimension, and conference graphs. Nederl. Akad. Wetensch. Indag. Math. 43(4), 385–391 (1981)
Read, R. C., Wilson, R. J.: An Atlas of Graphs, Oxford Science Publications. The Clarendon Press, Oxford University Press, New York (1998)
Robertson, N., Seymour, P. D., Thomas, R.: A survey of linkless embeddings, Graph structure theory (Seattle, WA, 1991). Contemp. Math., vol. 147, Amer. Math. Soc., Providence, RI, pp. 125–136 (1993). https://doi.org/10.1090/conm/147/01167
Schoenberg, I. J.: Remarks to Maurice Fréchet’s article “Sur la définition axiomatique d’une classe d’espace distanciés vectoriellement applicable sur l’espace de Hilbert” [MR1503246]. Ann. Math. (2), 36(3), 724–732 (1935). https://doi.org/10.2307/1968654
Acknowledgements
The author wishes to thank the two anonymous referees for many helpful comments and suggestions.
Funding
This work was supported by a University of South Florida Nexus Initiative Award.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors have not disclosed any competing interests.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Mitchell, L. On Euclidean Distances and Sphere Representations. Graphs and Combinatorics 39, 36 (2023). https://doi.org/10.1007/s00373-023-02636-w
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s00373-023-02636-w