# Binary Representations of Regular Graphs

Authors: Yury J. Ionin
Journal: International Journal of Combinatorics
 (2011)

---

## Abstract

For any 2-distance setX 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.


---

## Body

## 1. Introduction

The  subject of this paper is mutual relations between regular and strongly regular graphs, 2-distance sets in binary Hamming spaces, and quasisymmetric 1- and 2-designs.The following relation between strongly regular graphs and 2-distance sets in Euclidean spaces is well known (cf. [1, Theorem 2.23]): ifmis the multiplicity of the least eigenvalue of a connected strongly regular graphΓof ordern, then the vertex set ofΓcan be represented as a set of points, lying on a sphere inℝn-m-1, so that there exist positive real numbersh1<h2such that the distance between any two distinct vertices is equal toh1if they are adjacent as vertices ofΓand it is equal toh2otherwise. This result was recently generalized to all connected regular graphs in [2]. It has also been proved in [2] that, given n and m, such a representation of a connected regular graph in ℝn-m-2 is not possible.The notion of a 2-distance set representing a graph makes sense for any metric space, and the spaces of choice in this paper are the binary Hamming spaces. We will show (Theorem3.3) that the dimension of a binary Hamming space, in which a connected regular graph Γ can be represented, is at least n-m, where n and m have the same meaning as in the previous paragraph.It is also well known that the block graph of a quasisymmetric 2-design is strongly regular. However, many strongly regular graphs are not block graphs, and there is no good characterization of the graphs that are block graphs of quasisymmetric 2-designs. The situation changes if we consider the representation of graphs in binary Hamming spaces. We will show (Theorem4.6) that a connected strongly regular graph admits a representation in the binary Hamming space of the minimal dimension n-m if and only if it is the block graph of a quasisymmetric 2-design.At the dawn of graph theory there was a short-lived conjecture that a graph is determined by the spectrum of its adjacency matrix. Of course, it is not true (see a very interesting discussion in [3]). However, some classes of graphs can be described by their spectra. In particular, if a connected regular graph has the same spectrum as a line graph, then it is almost always a line graph itself (all exceptions are known). We will show (Corollary 5.7) that if a connected regular graph Γ is cospectral with a line graph L(G) of a graph G and, beside that, the minimal dimension of a binary Hamming space, in which either graph can be represented, is the same for Γ and L(G), then Γ is a line graph.


## 2. Preliminaries

All graphs in this paper are finite and simple, and all incidence structures are without repeated blocks. For a graphΓ, |Γ| denotes the order ofΓ, that is, the number of vertices. If x and y are vertices of a graph Γ, then x~y means that x and y are adjacent, while x≁y means that x and y are distinct and nonadjacent. Two graphs are said to be cospectral if their adjacency matrices have the same characteristic polynomial.Throughout the paper we useI to denote identity matrices and J to denote square matrices with every entry equal to 1. The order of I and J will be always apparent from the context. We denote as 0 and 1 vectors (columns, rows, points) with all entries (coordinates) equal to 0 or all equal to 1, respectively. In examples throughout the paper we will use digits and letters to denote elements of a small set and omit braces and commas when a subset of such a set is presented; for example, we will write 1350b instead of {1,3,5,0,b}.Ifn is a positive integer, then [n] denotes the set {1,2,…,n}.Definition 2.1.
Thebinary Hamming spaceHn consists of all n-tuples a=(a1,a2,…,an) with each ai equal to 0 or 1. When it is convenient, one identifies a with the set {i∈[n]:ai=1}. The distance h(a,b) between a and b=(b1,b2,…,bn)∈Hn is the number of indices i for which ai≠bi. The Euclidean norm of a vector x∈ℝn is denoted as ∥x∥, so, for a,b∈Hn, h(a,b)=∥a-b∥2.
A setX⊂Hn is called a 2-distance set if |{h(a,b):a,b∈X,a≠b}|=2.
Asphere with center c∈Hn and integer radius k, 1≤k≤n-1, is the set of all points x∈Hn such that h(c,x)=k. Any subset of a sphere (of radius k) is called a spherical set (of radiusk).Remark 2.2.
The sphere of radiusk in Hn, centered at a, coincides (as a set) with the sphere of radius n-k centered at the opposite point b=1-a. This allows us to assume, when needed, that the radius of a sphere does not exceed n/2. A sphere of radius k in Hn centered at 0, regarded as a subset of ℝn, is the intersection of the unit cube and the hyperplane x1+x2+⋯+xn=k.Remark 2.3.
Forn≥2, the distance between any two points of a spherical set in Hn is even.Definition 2.4.
Anincidence structure (without repeated blocks) is a pair D=(V,ℬ), where V is a nonempty finite set (of  points) and ℬ is a nonempty set of subsets of V (blocks). The cardinality of the intersection of two distinct blocks is called an intersection number of D. An incidence structure is said to be  quasisymmetric if it has exactly two distinct intersection numbers. For a nonnegative integer t, an incidence structure D is called a t-design if all blocks of D have the same cardinality and every set of t points is contained in the same number of blocks. A t-design D with an (points versus blocks) incidence matrix N is called  nonsquareif N is not a square matrix, and it is called  nonsingular if det(NN⊤)≠0. A 2-design is also called a (v,b,r,k,λ)-design, where v is the number of points, b is the number of blocks, r is the  replication number, that is, the number of blocks containing any given point, k is the block size, and λ is the number of blocks containing any given pair of points.
With any quasisymmetric incidence structure we associate itsblock graph.Definition 2.5.
IfD is a quasisymmetric incidence structure with intersection numbers α<β, then the  block graph of D is the graph whose vertices are the blocks of D and two vertices are adjacent if and only if the corresponding blocks meet in β points.Remark 2.6.
If a regular graph, other than a complete graph, is connected, then it has at least three distinct eigenvalues. It is strongly regular if and only if it has exactly three distinct eigenvalues. IfD is a quasisymmetric 2-design, then it is nonsquare and its block graph is strongly regular. If D is a quasisymmetric t-design with block size k and intersection numbers α<β, then N⊤N=(k-α)I+(β-α)A+αJ, where N is an incidence matrix of D and A is an adjacency matrix of the block graph of D. If D is a (v,b,r,k,λ)-design, then NN⊤=(r-λ)I+λJ. Therefore, det(NN⊤)=rk(r-λ)v-1≠0, so D is nonsingular. For these and other basic results on designs and regular graphs, see [1] or [4].Definition 2.7.
LetX={x1,x2,…,xb} be a 2-distance set of cardinality b in Hn, and let h1<h2 be the nonzero distances in X. One denotes as ΓX the graph whose vertex set is X and the edge set is the set of all pairs {xi,xj} with h(xi,xj)=h1. For i=1,2,…,b, let xi=(xi1,xi2,…,xin) and Bi={j∈[n]:xij=1}, so xi is the characteristic vector of Bi. Let ℬ={B1,B2,…,Bb}. One denotes as DX the incidence structure ([n],ℬ).Remark 2.8.
IfX is a spherical 2-distance set centered at 0, then the incidence structure DX is a quasisymmetric 0-design and ΓX is its block graph.Proposition 2.9.
LetX be a 2-distance set in Hn, and let h1<h2 be the nonzero distances in X. If the graph ΓX is connected, then h2≤2h1.Proof.
Supposeh2>2h1. If x,y, and z are distinct vertices of ΓX such that x~y and x~z, then the triangle inequality implies that y~z. Therefore, all neighbors of x form a connected component of ΓX. Since ΓX is not a complete graph, it is not connected; a contradiction.Definition 2.10.
One will say that a spherical 2-distance setX⊂Hn  represents a graphΓ  inHn if Γ is isomorphic to ΓX. The least n for which such a set X exists is called the  binary spherical representation number ofΓ and is denoted as bsr(Γ).Proposition 2.11.
Every simple graphΓ, except null graphs and complete graphs, admits a spherical representation in Hn if n is sufficiently large.Proof.
LetΓ be a noncomplete graph of order b with e≥1 edges, and let N=[nij] be an incidence matrix of Γ. For i=1,2,…,b, let Xi={j∈[e]:nij=1}. Let k=max{|Xi|:1≤i≤b}, and let Y1,Y2,…,Yb be pairwise disjoint subsets of {e+1,e+2,…,e+bk} such that |Yi|=k-|Xi|. For i=1,2,…,b, let xi=(xi1,xi2,…,xi,e+bk)∈He+bk, where xij=1 if and only if j∈Xi∪Yi. Then, for 1≤i<j≤b, the distance between points xi and xj is equal to 2(k-2) if the ith and jth vertices of Γ are adjacent, and it is equal to 2k otherwise. Since Γ is not a complete graph, the set {x1,x2,…,xb} is a 2-distance set representing Γ in He+bk, and this set lies on a sphere of radius k centered at 0.If the graphΓ in the above proof is regular, we do not need to add columns to its incidence matrix N.Proposition 2.12.
IfΓ is a noncomplete regular graph with e≥1 edges, then bsr(Γ)≤e.Theorem5.1 implies that if Γ is a cycle, then its binary spherical representation number equals the number of edges.For any graphG, the line graph ofG, denoted as L(G), is the graph whose vertex set is the edge set of G; two distinct vertices of L(G) are adjacent if and only if the corresponding edges of G share a vertex. Line graphs are precisely the graphs representable by spherical 2-distance sets of radius 2.Proposition 2.13.
A graphΓ can be represented in Hn by a spherical 2-distance sets of radius 2 if and only if Γ is isomorphic to the line graph of a graph of order n.Proof.
IfΓ=L(G), where G is a graph of order n, then the columns of an incidence matrix of G form a 2-distance subset of Hn of radius 2 representing Γ. Conversely, let X be a 2-distance subset of Hn of radius 2 centered at 0 and representing a graph Γ. Let G be a graph whose incidence matrix coincides with an incidence matrix of DX. Then |G|=n and Γ is isomorphic to L(G).Remark 2.14.
LetG be a regular graph of degree r, and let X be the set of columns of an incidence matrix N of G. Then DX is a quasisymmetric 1-design (with block size 2 and replication number r) and N is its incidence matrix. If r≥3, this design is non-square. The next result (Proposition 2.3 in [5]) yields a necessary and sufficient condition for this 1-design to be nonsingular.Proposition 2.15.
IfN is an incidence matrix of a graph Γ of order n and c is the number of connected components of Γ, then
(2.1)rank⁡(NN⊤)={n,ifΓisnotabipartitegraph,n-c,ifΓisabipartitegraph.


## 3. Lower Bounds

The main tool in obtaining a lower bound onbsr(Γ) is the following classical theorem of distance geometry.Definition 3.1.
LetX={x1,x2,…,xb} be a set of b points in ℝn.TheSchoenberg matrix ofXwith respect to a pointz∈ℝn is the matrix Sz(X)=[sij] of order b with
(3.1)sij=‖z-xi‖2+‖z-xj‖2-‖xi-xj‖2.Theorem 3.2 (see [6, 7]).
IfX is a finite set in ℝn, then, for any z∈ℝn, the Schoenberg matrix Sz(X) is positive semidefinite and rank(Sz(X))≤n.We will now derive a sharp lower bound on the binary spherical representation number of a connected regular graph.Theorem 3.3.
LetΓ be a connected regular graph, and let m be the multiplicity of the least eigenvalue of Γ. Then bsr(Γ)≥|Γ|-m. Moreover, bsr(Γ)=|Γ|-m if and only if Γ is the block graph of a nonsquare nonsingular quasisymmetric 1-design.Proof.
Letbsr(Γ)=n, and let Γ be isomorphic to ΓX, where X is a spherical 2-subset of Hn. Let h1<h2 be the nonzero distances in X and k the radius of a sphere in Hn containing X. Without loss of generality, we assume that this sphere is centered at 0. Then z=(k/n,k/n,…,k/n) is the center of an Euclidean sphere containing X. The radius of this sphere is equal to k(n-k)/n. Let A be an adjacency matrix of ΓX. Then the matrix
(3.2)S=Sz(X)=h2I+(h2-h1)A+(2k(n-k)n-h2)J
is the Schoenberg matrix of the set X with respect to z.
Letd be the degree of Γ, ρ0=d>ρ1>⋯>ρs=ρ all distinct eigenvalues of A, and m0=1,m1,…,ms=m their respective multiplicities. Then the eigenvalues of S are
(3.3)σ0=2|Γ|k(n-k)n-dh1-(|Γ|-d-1)h2,
with 1 as an eigenvector, and, for i=1,2,…,s,
(3.4)σi=h2+(h2-h1)ρi
(with eigenvectors orthogonal to 1). For 0≤i≤s, the multiplicity of σi is at least mi. (It is greater than mi if σi=σ0, i≠0.)
Theorem3.2 implies that all eigenvalues of S are nonnegative, so σi>0 for 1≤i≤s-1. Therefore, rank(S)≥∑i=1s-1mi=|Γ|-m-1. On the other hand, since both X and z lie in the hyperplane x1+x2+⋯+xn=k, Theorem 3.2 implies that rank(S)≤n-1, so n≥|Γ|-m.
Suppose now thatn=|Γ|-m. Then rank(S)=|Γ|-m-1, and therefore σs=σ0=0. From σ0=0 we derive
(3.5)2|Γ|k(n-k)=n(dh1+(|Γ|-d-1)h2).
The incidence structureDX=([n],ℬ) has n points, |Γ| blocks, all of cardinality k, and two intersection numbers, α=k-h2/2<β=k-h1/2. The graph Γ is the block graph of DX. Using h1=2(k-β) and h2=2(k-α), we transform (3.5) into
(3.6)(β-α)d=k(|Γ|kn-1)-α(|Γ|-1).
For eachi∈[n], let ri denote the number of blocks of DX containing i. Fix a block C and count in two ways pairs (B,i), where B∈ℬ, B≠C, and i∈C∩B:
(3.7)dβ+(|Γ|-d-1)α=∑i∈C(ri-1).
Using this equation and (3.6), we derive
(3.8)∑i∈Cri=dβ+(|Γ|-d-1)α+k=|Γ|k2n.
Therefore,
(3.9)∑C∈B∑i∈Cri=|Γ|2k2n.
Since each i∈[n] contributes ri2 into the left-hand side of this equation, we obtain that
(3.10)∑i=1nri2=|Γ|2k2n.
On the other hand, counting in two ways pairs(i,B) with B∈ℬ and i∈B yields
(3.11)∑i=1nri=∑B∈B|B|=|Γ|k.
Thus,
(3.12)(1n∑i=1nri)2=1n∑i=1nri2.
Therefore, ri=r=|Γ|k/n for i=1,2,…,n. Thus, DX is a quasisymmetric 1-design. (Note that we have derived this result from (3.5) rather than from a stronger equation rank(S)=|Γ|-m-1.) Since n<|Γ|, the 1-design DX is non-square, so we have to show that it is nonsingular.The incidence matrix N of DX satisfies the equation
(3.13)N⊤N=(k-α)I+(β-α)A+αJ.
Therefore, the eigenvalues of N⊤N are
(3.14)τ0=k-α+(β-α)ρ0+α|Γ|,τi=k-α+(β-α)ρi(1≤i≤s).
Since τ0>τ1>⋯>τs and since rank(N⊤N)≤n, we obtain that τs=0 and τi>0 for 0≤i≤s-1. Since the multiplicity of τs is the same as the multiplicity of ρs, we have rank(N⊤N)=n. Therefore, rank(NN⊤)=n, and then det(NN⊤)≠0, that is, DX is nonsingular.
Suppose now thatΓ is the block graph of a nonsquare nonsingular quasisymmetric 1-design D with intersection numbers α<β. The design D has less points than blocks, so let b be the number of blocks and b-m the number of points. We have to show that m is the multiplicity of the least eigenvalue of Γ and that bsr(Γ)=b-m.
LetN be an incidence matrix of D and X the set of all columns of N regarded as points in Hb-m. Then X is a 2-distance set and D is DX. The set X lies on a sphere of radius k centered at 0, where k is the cardinality of each block of D, and the nonzero distances in X are h1=2(k-β) and h2=2(k-α).
MatrixN satisfies (3.13) with A being an adjacency matrix of Γ. Let ρ0>ρ1>⋯>ρs be all distinct eigenvalues of A. Then the eigenvalues of N⊤N are given by (3.14). Since N⊤ has more rows than columns, we have τs=0. Since det(NN⊤)≠0, the sum of the multiplicities of the nonzero eigenvalues of N⊤N is b-m, so the multiplicity of τs is equal to m. Therefore, the multiplicity of ρs is equal to m, and then bsr(Γ)≥b-m. Since X is in Hb-m, we have bsr(Γ)=b-m.It has been shown in the course of this proof that ifbsr(Γ)=|Γ|-m, then σ0=0, which implies (3.5), and σs=0, which implies
(3.15)h2h1=ρρ+1.
In fact, (3.15) must hold whenever bsr(Γ)<|Γ|, because otherwise rank(A)≥|Γ|-1 and then bsr(Γ)≥|Γ|. If bsr(Γ)=|Γ| and (3.15) does not hold, then σ0=0. It has also been shown that if bsr(Γ)=|Γ|-m, then the replication number of the corresponding 1-design is |Γ|k/(b-m). We combine these observations in the following two theorems.Theorem 3.4.
LetΓ be a connected regular graph of order b and degree d, and let m be the multiplicity of the least eigenvalue ρ of Γ. Let bsr(Γ)=b-m, and let Γ be isomorphic to ΓX, where X is a 2-subset of Hb-m lying on a sphere of radius k centered at 0. Let h1<h2 be the nonzero distances in X. Then,(i)
2bk(b-m-k)=(b-m)(dh1+(b-d-1)h2);(ii)
h2/h1=ρ/(ρ+1);(iii)
DX is a nonsquare nonsingular quasisymmetric 1-design with b-m points, b blocks, block size k, replication number bk/(b-m), and intersection numbers k-h1/2 and k-h2/2.Theorem 3.5.
LetΓ be a connected regular graph of order b and degree d, and let ρ be the least eigenvalue of Γ. Let bsr(Γ)=n, and let Γ be isomorphic to ΓX, where X is a 2-subset of Hn lying on a sphere of radius k. Let h1<h2 be the nonzero distances in X:(i)
if2bk(n-k)=n(dh1+(b-d-1)h2), then DX is a quasisymmetric 1-design;(ii)
ifn<b, then h2/h1=ρ/(ρ+1);(iii)
ifn=b and h2/h1≠ρ/(ρ+1), then 2k(b-k)=dh1+(b-d-1)h2.Ifh2/h1=ρ/(ρ+1), then ρ is rational, so (ii) implies that the following useful result.Corollary 3.6.
If the least eigenvalue of a connected regular graphΓ is irrational, then bsr(Γ)≥|Γ|.An infinite family of regular graphs attaining the lower bound of Theorem3.3 is given in the following example.Example 3.7.
LetD be a (v,b,r,k,1)-design with b≥v+r and k≥3, and let D′ be an incidence structure obtained by deleting from D one point and all blocks containing this point. Then D′ is a 1-design with v-1 points, b-r>v-1 blocks of cardinality k, replication number r-1, and intersection numbers 0 and 1. Without loss of generality, we assume that the point set of D is [v], the deleted point is v, and the deleted blocks are
(3.16){1,2,…,k-1,v},{k,k+1,…,2k-2,v},…,{v-k+1,v-k+2,…,v}.
Let N be the corresponding incidence matrix of D′. Then NN⊤ is an r×r block matrix of (k-1)×(k-1) blocks with all diagonal blocks equal to (r-1)I and all off-diagonal blocks equal J. The spectrum of NN⊤ consists of eigenvalues (r-1)k of multiplicity 1, r-1 of multiplicity (k-2)r, and r-k of multiplicity r-1. Therefore, det(NN⊤)≠0; that is, the design D′ is nonsingular. The spectrum of N⊤N is obtained by adjoining the eigenvalue 0 of multiplicity b-r-v+1 to the spectrum of NN⊤. Since N⊤N=kI+A, where A is an adjacency matrix of the block graph Γ of D′, we determine that the multiplicities of the largest and the smallest eigenvalues of A are 1 and b-r-v+1, respectively. Therefore, Γ is a connected regular graph and bsr(Γ)=v-1.


## 4. Strongly Regular Graphs

For strongly regular graphs we first obtain a sharp upper bound for the binary spherical representation number.Proposition 4.1.
IfΓ is a connected strongly regular graph of order n, then bsr(Γ)≤n.Proof.
LetΓ be an srg(n,d,λ,μ), and let A be an adjacency matrix of Γ. Then A2=(d-μ)I+(λ-μ)A+μJ. Therefore, (A+I)2=(d-μ+1)I+(λ-μ+2)A+μJ. Let X be the set of rows of A+I regarded as points in Hn. Then the distance between two distinct points of X is equal to 2(d-λ-1) if the points correspond to adjacent vertices of Γ; otherwise, it is equal to 2(d-μ+1). Thus, X is a 2-distance set in Hn, lying on a sphere of radius d+1 centered at 0, and, if λ≥μ-1, then Γ is isomorphic to ΓX.
Ifλ≤μ-1, then let Y be the set of rows of the matrix J-A. The distance between two distinct points of Y is equal to 2(d-μ) if the points correspond to adjacent vertices of Γ; otherwise, it is equal to 2(d-λ). Therefore, Y is a 2-distance set in Hn, lying on a sphere of radius n-d centered at O, and Γ is isomorphic to ΓY.This proposition and Corollary3.6 imply the next result.Corollary 4.2.
If the least eigenvalue of a strongly regular graphΓ of order n is irrational, then bsr(Γ)=n.Remark 4.3.
The least eigenvalue of a strongly regular graph is irrational if and only if it is ansrg(n,(n-1)/2,(n-5)/4,(n-1)/4), where n≡1(mod4) is not a square. A graph with these parameters exists if and only if there exists a conference matrix of order n+1.Example 4.4.
LetΓ be the complement of the cycle C7. The least eigenvalue of Γ is irrational, so bsr(Γ)≥7. Suppose bsr(Γ)=7, and let Γ be isomorphic to ΓX, where X is a 2-subset of H7 with nonzero distances h1<h2, lying on a sphere of radius k centered at 0. Since h1 and h2 are even, h2≤7 and h2≤2h1 (Proposition 2.9), we have h1=2, h2=4 or h1=4, h2=6. In either case, Theorem 3.5(iii) yields an equation without integer solutions. Thus, bsr(Γ)≥8, so the strong regularity in Proposition 4.1 is essential.Remark 4.5.
There are 167 nonisomorphic strongly regular graphs with parameters(64,18,2,6) [8]. The least eigenvalue of these graphs is −6 of multiplicity 18. Theorem 3.3 and Proposition 4.1 imply that if Γ is any of these 167 graphs, then 46≤bsr(Γ)≤64. Therefore, there are nonisomorphic graphs with these parameters having the same binary spherical representation number.
Also, there are 41 nonisomorphic strongly regular graphs with parameters(29,14,6,7) [8]. The least eigenvalue of these graphs is irrational, so by Corollary 4.2 the binary spherical representation number of all these graphs is 29.
Theorem3.3 for regular graphs can be rectified if the graph is strongly regular.Theorem 4.6.
LetΓ be a connected strongly regular graph of order b, and let m be the multiplicity of the least eigenvalue of Γ. Then bsr(Γ)=b-m if and only if Γ is the block graph of a quasisymmetric 2-design.Proof.
IfΓ is the block graph of a quasisymmetric 2-design D, then Remark 2.6 and Theorem 3.3 imply that bsr(Γ)=b-m.
Suppose now thatbsr(Γ)=b-m, and let X be a spherical 2-distance subset of Hb-m representing Γ. Let h1<h2 be the nonzero distances in X and k the radius of the sphere centered at 0 and containing X. Every block of the incidence structure DX=([b-m],ℬ) is of cardinality k, the intersection numbers of D are α=k-h2/2<β=k-h1/2, and the replication number of D is r=bk/(b-m) (Theorem 3.4). The graph Γ is the block graph of D. Let ρ0=d>ρ1>ρ2 be the eigenvalues of Γ. Since Γ is connected, the multiplicity of ρ0 is 1. Since the multiplicity of ρ2 is m, the multiplicity of ρ1 is b-m-1.
LetA be an adjacency matrix of Γ. Theorem 3.4(ii) implies that (β-α)ρ2=(1/2)(h1-h2)ρ2=-(k-α). Since Tr(A)=d+(b-m-1)ρ1+mρ2=0, we use Theorem 3.4(i) to derive that
(4.1)(β-α)ρ1=α-k+r-λ,
where λ=r(k-1)/(b-m-1). Since k<b-m, we have λ<r.
LetN be an incidence matrix of DX. Then
(4.2)N⊤NJ=NN⊤J=krJ,N⊤N=(k-α)I+(β-α)A+αJ.
From these equations we determine the eigenvalues ofN⊤N: τ0=kr, τ1=k-α+(β-α)ρ1=r-λ, and τ2=k-α+(β-α)ρ2=0. Their respective multiplicities are 1, b-m-1, and m. Therefore, the eigenvalues of NN⊤ are τ0 of multiplicity 1 and τ1 of multiplicity b-m-1. Since NN⊤J=krJ, the eigenspace E0 of NN⊤ corresponding to the eigenvalue τ0 is generated by 1. Therefore, E1=E0⊥ is the eigenspace corresponding to the eigenvalue τ1. On the other hand, the matrix M=(r-λ)I+λJ has the same eigenvalues with the same respective eigenspaces. Thus, NN⊤=M, and therefore DX is a quasisymmetric 2-design with intersection numbers α and β. The graph Γ is the block graph of this design.Example 4.7.
TheCocktail Party graphCP(n) has 2n vertices split into n pairs with two vertices adjacent if and only if they are not in the same pair. It is the block graph of a quasisymmetric 2-design if and only if the design is aHadamard 3-design with n+1 points (cf. [4, Theorem 8.2.23]). The least eigenvalue of CP(n) is −2 of multiplicity n-1. By Theorem 4.6, bsr(CP(n))≥n+1 and bsr(CP(n))=n+1 if and only there exists a Hadamard matrix of order n+1. This example shows that it is hard to expect a simple general method for computing the binary spherical representation number of a strongly regular graph.


## 5. Line Graphs

In this section we determine the binary spherical representation number for the line graphs of regular graphs. IfN is an incidence matrix of a graph G, then N⊤N=2I+A, where A is an adjacency matrix of the line graph Γ=L(G). Let G be connected and have n vertices and e edges. If e>n, then the least eigenvalue of N⊤N is 0, and therefore the least eigenvalue of Γ is ρ=-2. Since matrices NN⊤ and N⊤N have the same positive eigenvalues, Proposition 2.15 implies that the multiplicity of ρ is equal to e-n if the graph G is not bipartite, and it is equal to e-n+1 if G is a connected bipartite graph. If e=n, then G is a cycle, so Γ=Cn is a cycle of order n too. If n is even, then the least eigenvalue of Cn is −2 of multiplicity 1; if n≥5 is odd, then the least eigenvalue of Cn is irrational. See [9] for details.Theorem 5.1.
IfΓ is the line graph of a connected regular graph of order n≥4, then bsr(Γ)=n.Proof.
LetΓ be the line graph of a connected regular graph G of order n≥4 and degree d. Then Γ is a connected regular graph of order nd/2 and degree 2d-2. The columns of an incidence matrix of G form a spherical 2-distance set in Hn representing Γ, so bsr(Γ)≤n.
Suppose first thatd=2, that is, G is Cn, and that n is odd. Then the least eigenvalue of Γ is irrational. Therefore, bsr(Γ)≥n by Corollary 3.6, so bsr(Γ)=n.
Suppose now thatd≥3 and the graph G is not bipartite. From Proposition 2.15, the multiplicity of the least eigenvalue of Γ is nd/2-n, and then Theorem 3.3 implies that bsr(Γ)≥n, so bsr(Γ)=n.
Suppose finally thatG is a bipartite graph (this includes the case G=Cn with even n). Then the least eigenvalue of Γ is −2 and its multiplicity is nd/2-n+1. Therefore, by Theorem 3.3, bsr(Γ)≥n-1. Suppose bsr(Γ)=n-1. Theorem 3.4(ii) implies that h2=2h1 and then the condition (i) of Theorem 3.4 can be rewritten as
(5.1)nk(n-1-k)=h1(n-1)(n-2).
If n is odd, then (n-1)(n-2) and n are relatively prime; if n is even, then (n-1)(n-2)/2 and n/2 are relatively prime. In either case, (n-1)(n-2)/2 divides k(n-1-k). However, k(n-1-k)≤(n-1)2/4<(n-1)(n-2)/2. Therefore, bsr(Γ)=n.The graphL2(n) is the line graph of the bipartite graph with the bipartition sets of cardinality n. The following corollary generalizes the well-known result [10] that these graphs are not block graphs of quasisymmetric 2-designs.Corollary 5.2.
The line graph of a connected regular graphG with more than three vertices is the block graph of a nonsquare nonsingular quasisymmetric 1-design if and only if G is not a cycle and is not a bipartite graph.Remark 5.3.
IfG is a semiregular connected bipartite graph of order n, then the graph L(G) is regular and bsr(L(G))=n or n-1. We do not know of any example when bsr(L(G))=n-1.There exist regular graphs that are cospectral with a line graph but are not line graphs. The complete list of such graphs is given in the following theorem.Theorem 5.4 (see [11]).
Let a regular graphΓ be cospectral with the line graph L(G) of a connected graph G. If Γ is not a line graph, then G is a regular 3-connected graph of order 8 or K3,6 or the semiregular bipartite graph of order 9 with 12 edges.Sincebsr(L(G))<10 for every graph G listed in Theorem 5.4, the next theorem implies that if a connected regular graph Γ is cospectral with a line graph L(G) and if bsr(Γ)=bsr(L(G)), then Γ is a line graph. The proof is based on the following theorem according to Beineke [12].Theorem 5.5.
A graph is a line graph if and only if it does not contain as an induced subgraph any of the nine graphs of Figure1.Figure 1Theorem 5.6.
Let the least eigenvalue of a connected regular graphΓ be equal to −2. If bsr(Γ)<10, then Γ is a line graph or the Petersen graph or CP(n) with 4≤n≤7.Proof.
The Petersen graphP is the block graph the quasisymmetric (6,10,5,3,2)-design, so bsr(P)=6. We also have bsr(CP(7))=8 (Example 4.7). For n=4,5, and 6, CP(n) is an induced subgraph of CP(8), so bsr(CP(n))≤8.
Letbsr(Γ)=n≤9, and let a 2-distance set X represent Γ in Hn. Let h1<h2 be the nonzero distances in X, and let X lie on a sphere of radius k centered at 0. Let f be an isomorphism from Γ to ΓX. For each vertex x of Γ we regard f(x) as a k-subset of [n].
SupposeΓ is not a line graph. Since the least eigenvalue of Γ is −2, Theorem 3.4 implies that h2=2h1. Since n≤9, we assume that k≤4. Proposition 2.13 implies that k≠2, so k=3 or 4. By Theorem 5.5, Γ contains one of the nine graphs of Figure 1 as an induced subgraph. All subgraphs of Γ considered throughout the proof are assumed to be induced subgraphs.
Case 1 : (h1=4. Then h2=8, and therefore k=4).
IfΓ contains a coclique xyz of size 3, then |f(x)∪f(y)∪f(z)|=12>n. This rules out subgraphs F1 and F4. If the subgraph induced by Γ on a set xyz of three vertices has only one edge, then |f(x)∪f(y)∪f(z)|=10>n. This rules out subgraphs F2, F5, F6, F7, F8, and F9.
SupposeΓ contains F3 as a subgraph. Suppose also that every subgraph of order 3 of Γ has at least two edges. We assume without loss of generality that f(q)=1234 and f(s)=5678. Let x be a vertex of Γ, x≠q and x≠s. Since the subgraph with the vertex set qsx has at least two edges, x is adjacent to both q and s. Therefore, f(x) is a 4-subset of 12345678 for every vertex x of Γ. This implies that x is not adjacent to at most one other vertex. Since Γ is regular and not complete, Γ is a cocktail party graph CP(m). Therefore, m+1≤bsr(Γ)≤9 and bsr(Γ)≠m+1 for m=8 (Example 4.7). Since CP(2) and CP(3) are line graphs (of C4 and K4, resp.), we have 4≤n≤7.Case 2 (h1=2 and k=3).
SupposeΓ contains F1 as a subgraph. We let f(p)=123, f(q)=124, f(r)=135, and f(s)=236. Since the degree of q in F1 is 1 and the degree of p is 3, Γ has vertices q1 and q2 adjacent to q but not to p. Then f(q1)=146 and f(q2)=245. Similarly, we find vertices r1 and r2 adjacent to r but not to p and vertices s1 and s2 adjacent to s but not to p and assume that f(r1)=345, f(r2)=156, f(s1)=256, and f(s2)=346. The set U of the 10 vertices that we have found is the vertex set of a Petersen subgraph of Γ. The set f(U) consists of ten 3-subsets of 123456, no two of which are disjoint. Therefore, if Γ has a vertex v∉U, then f(v) is disjoint from at least one of the sets f(x), x∈U; a contradiction. Thus, Γ is the Petersen graph.
IfΓ contains F2 as a subgraph, we let f(p)=123 and f(r)=145. Then f(q),f(s),f(t)∈{124,125,134,135}. Since |f(q)∩f(s)|=|f(t)∩f(s)|=1, there is no feasible choice for f(s).
IfΓ contains F3 as a subgraph, we assume that f(p)=123, f(q)=124, and f(s)=135. Then f(r),f(t)∈{125,134}, and therefore |f(r)∩f(t)|≠2.
LetΓ contains F4 as a subgraph. Suppose first that f(p)∩f(q)∩f(s)≠∅. Then we assume that f(p)=123, f(q)=145, f(s)=167, f(t)=124, and f(u)=136, and there is no feasible choice for f(r). Suppose now that f(p)∩f(q)∩f(s)=f(r)∩f(q)∩f(s)=∅. We assume that f(p)=123, f(q)=145, and f(s)=246. Then f(t)=125 or 134. If f(t)=125, then f(u)=234 and f(r)=235. Γ has distinct vertices q1 and q2 adjacent to q but not to r, and we have f(q1)=f(q2)=156; a contradiction. If f(t)=134, then f(u)=126 and f(r)=136. Γ has distinct vertices q1 and q2 adjacent to q but not to t, and we have again f(q1)=f(q2)=156.
IfΓ contains F5 as a subgraph, we let f(p)=123, f(q)=145, and f(t)=124. Then f(r)=234 or 126, and in either case f(s)=f(u).
IfΓ contains F6 as a subgraph, we let f(p)=123, f(q)=124, and f(s)=135. Then we assume that f(r)=125. This implies f(u)=235 and f(t)=126. Γ has distinct vertices q1 and q2 adjacent to q but not to r. Then f(q1)=134 and f(q2)=234, so both q1 and q2 are adjacent to p. Since q1≁u and q2~u, Γ has three distinct vertices ui adjacent to u but not to p. However, f(ui)=245 for all these vertices.
IfΓ contains F8 as a subgraph, we let f(p)=123 and f(q)=124 and assume that f(s)=156 or 345. If f(s)=156, then f(r)=135, f(u)=136, and there is no feasible choice for f(t). If f(s)=345, then f(r)=135, f(u)=235, and again there is no feasible choice for f(t).
SupposeΓ contains F7 or F9 as a subgraph. We let f(p)=123, f(q)=124, and f(t)=135. Then f(r)=146 or 245 and f(s)=156 or 345, respectively. In either case, there is no feasible choice for f(u).Case 3 (h1=2 and k=4).
SupposeΓ contains F1 as a subgraph. We let f(p)=1234, f(q)=1235, f(r)=1246, and f(s)=1347. Γ has vertices q1 and q2 adjacent to q but not to p. Then f(q1)=1257 and f(q2)=1356. Similarly, we find vertices r1 and r2 adjacent to r but not to p and vertices s1 and s2 adjacent to s but not to p and assume that f(r1)=1267, f(r2)=1456, f(s1)=1367, and f(s2)=1457. The ten vertices that we have found form a Petersen subgraph of Γ. If 1∈f(x) for every vertex x of Γ, then we delete 1 from each f(x) and refer to Case 2. Suppose that there is a vertex x with 1∉f(x). Then the 4-set f(x) must meet each of the sets 234,235,246,347,257,356,267,456,367, and 457 in at least two points. Thus, there is no feasible choice for f(x).
IfΓ contains F2 as a subgraph, we let f(p)=1234, f(q)=1235, and f(r)=1256. Then f(s)=1246 and there is no feasible choice for f(t).
IfΓ contains F3 as a subgraph, we assume that f(p)=1234, f(q)=1235, and f(s)=1246. Then f(r),f(t)∈{1236,1245}, and therefore |f(r)∩f(t)|=2; a contradiction.
IfΓ contains F4 as a subgraph, we let f(p)=1234, f(t)=1235, f(u)=1246, f(r)=1236, and f(q)=1257. Then f(s)=1456. Let s1 and s2 be vertices of Γ adjacent to s but not to u. Then f(s1)=1345 and f(s2)=1356, and there is no feasible choice for f(v), where v~q and v≁t.
IfΓ contains F5 as a subgraph, we let f(p)=1234, f(q)=1256, and f(t)=1235. Then we may assume that either f(s)=1346 and f(u)=2346 or f(s)=1247 and f(u)=1248. In either case, there is no feasible choice for f(r).
SupposeΓ contains F6 as a subgraph. We let f(p)=1234 and f(r)=1235. Then f(q),f(s),f(t),f(u)∈{1245,1345,2345}∪{123α:α≥6}. Since the subgraph induced on qstu is triangle-free, we let f(q)=1236, f(t)=1237, f(s)=1245, and f(u)=1345. Let q1 and q2 be distinct vertices of Γ adjacent to q but not to p. Then f(qi)∈{1256,1356,2356}, so both q1 and q2 are adjacent to r but not to t. Therefore, Γ has at least four vertices ti adjacent to t but not to r. However, f(ti)∈{1247,1347,2347}; a contradiction.
IfΓ contains F8 as a subgraph, we let f(p)=1234, f(q)=1235, and f(r)=1246. Then (f(t),f(u))∈{(1236,1247),(1245,1346),(1245,2346)}, and there is no feasible choice for f(s).
SupposeΓ contains F7 or F9 as a subgraph. We let f(p)=1234, f(q)=1235, and f(t)=1246. Then f(r)∈{1356,2356}∪{125α:α≥7} and f(s)∈{1456,2456}∪{126α:α≥7}, so we assume that (f(r),f(s))∈{(1257,1267),(1356,1456),(2356,2456)}. In each case, there is no feasible choice for f(u).Corollary 5.7.
LetΓ be a connected regular graph cospectral with a line graph L(G) of a connected graph G. If bsr(Γ)=bsr(L(G)), then Γ is a line graph.Proof.
IfG is not an exceptional graph from Theorem 5.4, then Γ is a line graph by that theorem. If G is one of the exceptional graphs, then bsr(L(G))<10 and L(G) has more edges than vertices. Therefore, the least eigenvalue of L(G) is −2. Since the Petersen graph and graphs CP(n) are not exceptional, Theorem 5.6 implies that Γ is a line graph.Example 5.8.
LetX be the set of all points of H5 with even sum of coordinates. It is a 2-distance set and ΓX is the complement of the  Clebsch graph. The least eigenvalue of ΓX is −2, and, since it is not a line graph, Theorem 5.6 implies that bsr(ΓX)≥10 (so X is not spherical). Let Y be the set of all points (y1,y2,…,y10)∈H10 such that ∑i=15yi is even and yi+yi+5=1 for i=1,2,3,4,5. Then Y is a spherical 2-distance set and ΓY is isomorphic to ΓX. Thus, bsr(ΓX)=10.Example 5.9.
TheShrikhande graph is cospectral with L2(4), and the three  Chang graphs are cospectral with T(8), the line graph of K8, so we have examples of cospectral strongly regular graphs with distinct binary spherical representation numbers. It can be shown that the binary spherical representation number of the Shrikhande graph is 12.



---

*Source: 101928-2011-10-11.xml*