On representations of graphs as two-distance sets

DOI10.1016/J.DISC.2019.07.003zbMATH Open1429.05146arXiv1808.05915OpenAlexW2964123572MaRDI QIDQ2279265FDOQ2279265

Authors: Abdo Y. Alfakih 

Publication date: 12 December 2019

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: Let a eq b be two positive scalars. A Euclidean representation of a simple graph G in R^r is a mapping of the nodes of G into points in R^r such that the squared Euclidean distance between any two points is a if the corresponding nodes are adjacent and b otherwise. A Euclidean representation is spherical if the points lie on an (r-1)-sphere, and is J-spherical if this sphere has radius 1 and a=2 < b. Let dim_E(G), dim_S(G) and dim_J(G) denote, respectively, the smallest dimension r for which G admits a Euclidean, spherical and J-spherical representation. In this paper, we extend and simplify the results of Roy[18] and Nozaki and shinohara[17] by deriving exact simple formulas for dim_E(G) and dim_S(G) in terms of the eigenvalues of V^TAV, where A is the adjacency matrix of G and V is the matrix whose columns form an orthonormal basis for the orthogonal complement of the vector of all 1's. We also extend and simplify the results of Musin [16] by deriving explicit formulas for determining the J-spherical representation of G and for determining dim_J(G)in terms of the largest eigenvalue of �ar{A}, the adjacency matrix of the complement graph �ar{G}. As a byproduct, we obtain several related results and in particular we answer a question raised by Musin in [16].

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

Recommendations

• Graph representations, two-distance sets, and equiangular lines
• scientific article; zbMATH DE number 1409224
• Distance-two labelings of graphs
• Publication:3199436
• Graphs and spherical two-distance sets
• On representations of some thickness-two graphs
• Distance two labeling of the composition of graphs
• Characterizing 2-distance graphs
• On set intersection representations of graphs
• On the dimension to represent a graph by a unit distance graph

zbMATH Keywords

Euclidean distance matricesEuclideanspherical and \(J\)-spherical representationsspherical EDMstwo-distance sets

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Remarks to Maurice Frechet's article ``Sur la definition axiomatique d'une classe d'espaces vectoriels distancies applicables vectoriellement sur l'espace de Hilbert
• Title not available (Why is that?)
• Title not available (Why is that?)
• Properties of Euclidean and non-Euclidean distance matrices
• On certain linear mappings between inner-product and squared-distance matrices
• Circum-Euclidean distance matrices and faces
• Two theorems on Euclidean distance matrices and Gale transform
• Spherical codes and designs
• Title not available (Why is that?)
• An upper bound for the cardinality of an s-distance subset in real Euclidean space. II
• New maximal two-distance sets
• Title not available (Why is that?)
• Minimal Euclidean representations of graphs
• Title not available (Why is that?)
• Distance matrices and regular figures
• On rigidity and realizability of weighted graphs
• A geometrical characterization of strongly regular graphs
• Graphs and spherical two-distance sets
• Euclidean distance matrices and their applications in rigidity theory

Cited In (6)

• On a problem of Specker about Euclidean representations of finite graphs
• On Euclidean distances and sphere representations
• Geometric representations of graphs
• Two-distance-primitive graphs
• Graphs and spherical two-distance sets
• Vector representations of graphs

This page was built for publication: On representations of graphs as two-distance sets

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