Minimal Euclidean representations of graphs
Author:
Preprint
Abstract
A simple graph G is said to be representable in a real vector space of dimension m if there is an embedding of the vertex set in the vector space such that the Euclidean distance between any two distinct vertices is one of only two distinct values a or b, with distance a if the vertices are adjacent and distance b otherwise. The Euclidean representation number of G is the smallest dimension in which G is representable. In this note, we bound the Euclidean representation number of a graph using multiplicities of the eigenvalues of the adjacency matrix. We also give an exact formula for the Euclidean representation number using the main angles of the graph.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Topics in Algebraic Graph Theory, by Lowell W. Beineke and Robin J. Wilson (Academic Consultant: Peter J. Cameron), Encyclopedia of Mathematics and its Applications 102, CUP 2005, 257pp., £ 50.00/$95.00Combinatorics, Probability and Computing, 2006
- Spectra of random graphs with given expected degreesProceedings of the National Academy of Sciences, 2003
- Algebraic Graph Theory2001
- Solving Euclidean Distance Matrix Completion Problems Via Semidefinite ProgrammingComputational Optimization and Applications, 1999
- New Maximal Two-Distance SetsJournal of Combinatorial Theory, Series A, 1997
- A study of eigenspaces of graphsLinear Algebra and its Applications, 1993
- Designs, Graphs, Codes and their Links1991
- The cone of distance matricesLinear Algebra and its Applications, 1991
- Distance matrices, dimension, and conference graphsIndagationes Mathematicae, 1981
- Note sur le problème de UlamJournal of Combinatorial Theory, Series B, 1979