![](/images/graphics-bg.png)
Binary Representations of Regular Graphs
Author
Source
International Journal of Combinatorics
Issue
Vol. 2011, Issue 2011 (31 Dec. 2011), pp.1-15, 15 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2011-10-11
Country of Publication
Egypt
No. of Pages
15
Main Subjects
Abstract EN
For any 2-distance set X in the n-dimensional binary Hamming space Hn, let Γ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 Γ, or bsr(Γ), is the least n such that Γ is isomorphic to ΓX, where X is a 2-distance set lying on a sphere in Hn.
It is shown that if Γ is a connected regular graph, then bsr(Γ)≥b−m, where b is the order of Γ and m is the multiplicity of the least eigenvalue of Γ, and the case of equality is characterized.
In particular, if Γ is a connected strongly regular graph, then bsr(Γ)=b−m if and only if Γ 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.
American Psychological Association (APA)
Ionin, Yury J.. 2011. Binary Representations of Regular Graphs. International Journal of Combinatorics،Vol. 2011, no. 2011, pp.1-15.
https://search.emarefa.net/detail/BIM-446421
Modern Language Association (MLA)
Ionin, Yury J.. Binary Representations of Regular Graphs. International Journal of Combinatorics No. 2011 (2011), pp.1-15.
https://search.emarefa.net/detail/BIM-446421
American Medical Association (AMA)
Ionin, Yury J.. Binary Representations of Regular Graphs. International Journal of Combinatorics. 2011. Vol. 2011, no. 2011, pp.1-15.
https://search.emarefa.net/detail/BIM-446421
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-446421