Minimal Euclidean representations of graphs

DOI10.1016/J.DISC.2009.09.005MaRDI QIDQ965947zbMATH OpenOpenAlexFDO

Authors Aidan Roy

Publication date 27 April 2010

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0812.3707

zbMATH Keywords

algebraic graph theoryEuclidean 2-distance setEuclidean representationgraph eigenvaluegraph spectrummain anglemain eigenvaluerepresentable graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

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.

Recommendations

• scientific article; zbMATH DE number 64790
• Minimum difference representations of graphs
• Geometric Representation of Graphs in Low Dimension
• Minimal translation graphs in semi-Euclidean space
• scientific article; zbMATH DE number 681028
• Minimal graphs in \(M \times \mathbb{R}\)
• On minimal complex classes of graphs
• Graphs as r-minoes
• On minimal Folkman graphs
• Graph minor theory

Cites work

• An upper bound for the cardinality of an s-distance subset in real Euclidean space. II
• Chromatic number and the 2-rank of a graph
• Developments in the theory of graph spectra
• Eigenspaces of graphs
• scientific article; zbMATH DE number 4177110 (Why is no real title available?)
• scientific article; zbMATH DE number 3827893 (Why is no real title available?)
• scientific article; zbMATH DE number 3895787 (Why is no real title available?)
• scientific article; zbMATH DE number 3774424 (Why is no real title available?)
• scientific article; zbMATH DE number 50655 (Why is no real title available?)
• scientific article; zbMATH DE number 3590036 (Why is no real title available?)
• scientific article; zbMATH DE number 740754 (Why is no real title available?)
• scientific article; zbMATH DE number 2123603 (Why is no real title available?)
• scientific article; zbMATH DE number 3259777 (Why is no real title available?)
• scientific article; zbMATH DE number 3349884 (Why is no real title available?)
• scientific article; zbMATH DE number 3377258 (Why is no real title available?)
• scientific article; zbMATH DE number 3194323 (Why is no real title available?)
• Matrix Analysis
• Metric Spaces and Positive Definite Functions
• New maximal two-distance sets
• Note sur le problème de Ulam
• On Two-Distance Sets in Euclidean Space
• Properties of Euclidean and non-Euclidean distance matrices
• Solving Euclidean distance matrix completion problems via semidefinite progrmming
• Spectra of random graphs with given expected degrees
• The cone of distance matrices

Cited in

(18)

• A geometrical characterization of strongly regular graphs
• Complex spherical codes with three inner products
• On representations of graphs as two-distance sets
• Graphs and spherical two-distance sets
• On a problem of Specker about Euclidean representations of finite graphs
• The two-distance sets in dimension four
• scientific article; zbMATH DE number 1670673 (Why is no real title available?)
• scientific article; zbMATH DE number 681028 (Why is no real title available?)
• Gershgorin disks for multiple eigenvalues of non-negative matrices
• Geometric representations of graphs
• Complex spherical codes with two inner products
• Minimal Representations of Order Types by Geometric Graphs
• On Minimizing One Dimension of Some Two-Dimensional Geometric Representations of Plane Graphs
• Binary representations of regular graphs
• Spectral conditions for spherical 2-distance sets
• Euclidean sets with only one distance modulo a prime ideal
• Pseudo-Euclidean representations of switching classes of Johnson and Hamming graphs with minimal dimension
• Minimum difference representations of graphs

This page was built for publication: Minimal Euclidean representations of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q965947)