Minimal Euclidean representations of graphs |
| |
Authors: | Aidan Roy |
| |
Affiliation: | Department of Mathematics and Statistics & Institute for Quantum Information Science, University of Calgary, Calgary, Alberta T2N 1N4, Canada |
| |
Abstract: | A simple graph G is 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, α and β, with distance α if the vertices are adjacent and distance β 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: | Representable graph Euclidean representation Graph eigenvalue Main angle Main eigenvalue Graph spectrum Algebraic graph theory Euclidean 2-distance set |
本文献已被 ScienceDirect 等数据库收录! |
|