Summary: For any 2-distance set \(X\) in the \(n\)-dimensional binary Hamming space \(H_n\), let \(\Gamma_X\) be the graph with \(X\) as the vertex set and with two vertices adjacent if and only if the distance between them is the smaller of the two nonzero distances in \(X\). The binary spherical representation number of a graph \(\Gamma\), or \(\text{bsr}(\Gamma)\), is the least \(n\) such that \(\Gamma\) is isomorphic to \(\Gamma_X\), where \(X\) is a 2-distance set lying on a sphere in \(H_n\). It is shown that if \(\Gamma\) is a connected regular graph, then \(\text{bsr}(\Gamma) \geq b - m\), where \(b\) is the order of \(\Gamma\) and \(m\) is the multiplicity of the least eigenvalue of \(\Gamma\), and the case of equality is characterized. In particular, if \(\Gamma\) is a connected strongly regular graph, then \(\text{bsr}(\Gamma) = b - m\) if and only if \(\Gamma\) is the block graph of a quasisymmetric 2-design. It is also shown that if a connected regular graph is cospectral with a line graph and has the same binary spherical representation number as this line graph, then it is a line graph.
- Characterizations of derived graphs
- Combinatorics of symmetric designs
- scientific article; zbMATH DE number 50655 (Why is no real title available?)
- scientific article; zbMATH DE number 740754 (Why is no real title available?)
- scientific article; zbMATH DE number 3080144 (Why is no real title available?)
- Minimal Euclidean representations of graphs
- Remarks to Maurice Frechet's article ``Sur la definition axiomatique d'une classe d'espaces vectoriels distancies applicables vectoriellement sur l'espace de Hilbert
- Signless Laplacians of finite graphs
- Strongly Regular Graphs Derived from Combinatorial Designs
- Which graphs are determined by their spectrum?
This page was built for publication: Binary representations of regular graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q666512)
