1-Homogeneous Graphs with Cocktail Party µ -Graphs
ALEKSANDAR JURI ˇSI ´C [email protected]
IMFM and Nova Gorica Polytechnic, Slovenia
JACK KOOLEN [email protected]
Division of Applied Mathematics, KAIST, Daejeon, South Korea Received September 19, 2000; Revised December 3, 2002
Abstract. Letbe a graph with diameterd≥2. Recallis 1-homogeneous (in the sense of Nomura) whenever for every edgexyofthe distance partition
{{z∈V()|∂(z,y)=i, ∂(x,z)= j} |0≤i,j≤d}
is equitable and its parameters do not depend on the edgexy. Letbe 1-homogeneous. Thenis distance-regular and also locally strongly regular with parameters (v,k, λ, µ), wherev = k,k = a1,(v −k −1)µ = k(k −1−λ) andc2≥µ +1, since aµ-graph is a regular graph with valencyµ. Ifc2=µ +1 andc2=1, thenis a Terwilliger graph, i.e., all theµ-graphs ofare complete. In [11] we classified the Terwilliger 1- homogeneous graphs withc2≥2 and obtained that there are only three such examples. In this article we consider the casec2 =µ +2≥3, i.e., the case when theµ-graphs ofare the Cocktail Party graphs, and obtain that eitherλ =0, µ =2 oris one of the following graphs: (i) a Johnson graphJ(2m,m) withm≥2, (ii) a folded Johnson graph ¯J(4m,2m) withm≥3, (iii) a halvedm-cube withm≥4, (iv) a folded halved (2m)-cube with m≥5, (v) a Cocktail Party graphKm×2withm≥3, (vi) the Schl¨afli graph, (vii) the Gosset graph.
Keywords: distance-regular graph, 1-homogeneous, Cocktail Party graph, Johnson graph
1. Introduction
We study 1-homogeneous graphs in the sense of Nomura [16] (defined later in this section).
Some examples of such graphs are distance-regular graphs with at most onei, such that ai = 0 (e.g. bipartite graphs, complete multipartite graphs Km×t and generalized Odd graphs, in particular triangle free strongly regular graphs), regular near (2n)-gons (i.e., distance-regular graphs with ai = cia1 for alli and no induced K1,2,1), Taylor graphs (antipodal distance-regular 2-covers of complete graphs with diameter three), the Johnson graphsJ(2d,d), the folded Johnson graphs ¯J(4d,2d), the halvedn-cubes, the folded halved (4n)-cubes and 3-valent distance-regular graphs [11, Proposition 3.5].
Letbe a graph with diameter at least 2, and letx,ybe vertices ofat distance 2.
Then theµ-graphofxandyis the subgraph ofinduced by their common neighbours.
Let be 1-homogeneous. Then is distance-regular, locally strongly regular and, by [11, Proposition 2.1], the local graphs have the same parameters. Let us denote them by (v,k, λ, µ). Obviously, we havev = k,k = a1,(v −k −1)µ = k(k −1−λ)
andc2≥µ +1, since aµ-graph is a regular graph with valencyµ by [9, Theorem 3.1].
The casec2 =µ +1≥ 2, i.e., the case whenis a Terwilliger graph, was classified in [11]. Theµ-graphs of Terwilliger graphs are complete graphs. Since many of the above mentioned examples of 1-homogeneous graphs have the property that theirµ-graphs are complete multipartite graphs, it is natural to study 1-homogeneous graphs or even some more general graphs satisfying this property. Alternative motivation comes from the study of extended generalized quadrangles, see for example [5] and [22].
We establish some general properties of distance-regular graphs with certain local struc- ture, parameters and eigenvalues. There are some families of 1-homogeneous graphs for which we can show that theirµ-graphs are complete multipartite. One such (obvious) ex- ample is the casec2 = µ +2 ≥ 3, i.e., the case when theµ-graphs are Cocktail Party graphs. In this case we show that eitherλ =0 andµ =2 or the smallest eigenvalue of each local graph is−2 and so, by Seidel’s classification [17], [3, Theorem 3.12.4], eitherλ =0 andµ =2 or each local graph ofis one of the well known strongly regular graphs. In the latter case we show thatmust be one of the well known distance-regular graphs. Before we state the precise statement of our main result, we establish some notation and review basic definitions, for more details see Brouwer, Cohen and Neumaier [3], and Godsil [8].
At the end of this section we describe the organization of this paper.
Let us first recall that anequitable partitionof a graph is a partitionπ = {P1, . . . ,Ps} of its vertices into cells, such that for alli,j ∈ {1, . . . ,s}the numberci j of neighbours, which a vertex in the cell Pi has in the cell Pj, is independent of the choice of the vertex in Pi. Letbe a connected graph with diameterd. For a vertexx ofwe definei(x) to be the set of vertices at distancei from x, and set(x) = 1(x). For y ∈ i(x) and integers jandhwe defineDhj(x,y)=j(x)∩h(y) and pijh(x,y)= |Dhj(x,y)|. Then isi-homogeneousin the sense of Nomura [16] when the distance partition corresponding to any pairx,yof vertices at distancei, i.e., the collection of nonempty setsDhj(x,y), is an equitable partition, and the parameters corresponding to all such equitable partitions are independent of verticesxandyat distancei. Note that the graphis 0-homogeneous if and only if it isdistance-regular, and that ifis 1-homogeneous then it is distance-regular.
Letbe a graph. As usually, we denote the distance between verticesxandyofby
∂(x,y). Ifx,yandzare vertices ofsuch that∂(x,y)=1, ∂(x,z)=∂(y,z)=2, then we define a (triple) intersection numberα(x,y,z)= |(x)∩(y)∩(z)|(see figure 2.1(b) and (c) and also figure 1.1). We say that the parameterαofexistswhenα=α(x,y,z) for all triples of vertices (x,y,z) of such that∂(x,y) = 1,∂(x,z) = ∂(y,z) = 2. If is 1-homogeneous graph with diameterd ≥ 2 anda2 = 0, then αexists. A strongly regular graph witha2 = 0, that is locally strongly regular is 1-homogeneous if and only ifαexists (see figure 1.1(a)). Similarly, we say that the intersection number pijhexistsin a graphif pjhi(x,y)= pjhi for all pairs of verticesx andyat distancei. Of course, if is distance-regular, then for alli,j andhthe numbers pijhexist. Letai(x,y) :=p1ii (x,y), bi(x,y) :=p1i,i+1(x,y) andci(x,y) :=pi1,i−1(x,y).
For a vertexxof a graphwe define thelocal graph(x) as the subgraph of, induced by the neighbours ofx. Ifis distance-regular, then(x) hask=b0vertices and valency a1. LetCbe a graph (or a class of graphs). The graphis said to belocally(resp.µ-locally) C, when each local graph (resp. eachµ-graph) ofis isomorphic to (or a member of)C.
Figure 1.1. Letbe a strongly regular graph (v,k,a1,c2) witha2=k−c2=0. Thenis 1-homogeneous, i.e., it is a locally strongly regular graph (v,k, λ, µ), and for whichαexists, if and only if its complement is 2-homogeneous. For the second subconstituent of the complement ofis isomorphic to the complement of a local graph ofand for verticesxandyofat distance 2 a vertex inD11(x,y) hasa1−αneighbours in the set D22(x,y). (a) the distance partition of 1-homogeneous graphcorresponding to two adjacent vertices; (b) the distance partition of the complement of 1-homogeneous graph, corresponding to two vertices at distance 2, wherea1=v−2k+c2−2,c2=v−2k+a1,λ=k−2a1+µ−2,µ=k−2a1+λ, ¯k=kb1/c2and ¯k−b1= a2b1/c2.
Figure 1.2. A tower of graphs with their distance partitions corresponding to two adjacent vertices (all but the last one are 1-homogeneous graphs): (a) the Gosset graph is a unique distance-regular graph with intersection array{27,10,1; 1,10,27}, an antipodal 2-cover of the complete graphK28, and it is locally Schl¨afli graph see [3, pp. 103, 313]; (b) the Schl¨afli graph is a unique strongly regular graph (27, 16, 10, 8) and it is locally halved 5-cube, see [3, p. 103]; (c) the halved 5-cube, also known as the Clebsch graph, is a unique strongly regular graph (16, 10, 6, 6) and it is locallyJ(5, 2), i.e., the complement of the Petersen graph, see [3, p. 264] (so the local graph is not 1-homogeneous), the Johnson graphJ(5, 2) is a unique strongly regular graph (10, 6, 3, 4) and is locally the 3-prism; (d) the 3-prism has two different distance partitions corresponding to an edge.
Note that the distance partition of the Gosset graph corresponding to two adjacent vertices is at the same time also its distance partition corresponding to two vertices at distance 2 (actually, in general, a 1-homogeneous 2-cover with diameterDis also (D−1)-homogeneous).
We are now ready to state the main result of this paper.
Theorem 1.1 Let be a1-homogeneous graph with diameter d ≥ 2. Recall that for each vertex x ofthe local graph(x)is strongly regular with parameters independent of x; we denote these parameters by (v,k, λ, µ). If c2 = µ +2 ≥ 3, then either λ =0, µ =2,d≥3andα=1,oris one of the following graphs:
(i) a Johnson graph J(2m,m)with m≥2,
(ii) a folded Johnson graph J(4m,¯ 2m)with m ≥2, (iii) a halved m-cube with m≥4,
(iv) a folded halved(4m)-cube with m ≥2, (v) a Cocktail Party graph Km×2with m≥3,
(vi) the Schl¨afli graph with intersection array{16,5; 1,8}, (vii) the Gosset graph with intersection array{27,10,1; 1,10,27}.
Remark The Gosset graph is locally the Schl¨afli graph, see figure 1.2.
The graphin the above statement is µ-locally the Cocktail Party graph. Our study is part of a larger project to classify 1-homogeneous graphs that areµ-locally complete mul- tipartite. There are also very interesting examples of 1-homogeneous graphs that areµ- locally several copies of complete multipartite graphs or even the 2-extension of the halved 5-cube.
The multipartite graphKt×nis the complement oftcliques of sizen, i.e., the multipartite graph Kn1,n2,...,nt with n1 = n2 = · · · = nt = n. In particular, Kt×2 is the Cocktail Party graph. Let be a distance-regular graph with diameter d ≥ 2 and eigenvalues θ0 > θ1 > · · · > θd. An easy eigenvalue interlacing argument guaranteesθ1 ≥ 0 and θd ≤ −√
2. We say thatistightwhenever it is not bipartite and k(a1+b+b−)=(a1−b+)(a1−b−),
where
b+= −1− b1
1+θd
and b−= −1− b1
1+θ1
.
Ford =2 we haveb1= −(1+θ1)(1+θ2),b+=θ1,b− =θ2, and thereforeis tight (i.e., θ1=0) if and only if it is a complete multipartite graphKt×n witht >2 (i.e.,a1=0 and µ =k). Tight graphs of diameterd ≥3 were characterized in a number of ways in [10].
For example, ifis a distance-regular graph with diameterd ≥ 2, thenis tight if and only ifis 1-homogeneous witha1 =0 andad =0. Some examples of tight graphs are the Patterson graph and 10 tight antipodal distance-regular graphs with diameter four.
Corollary 1.2 Letbe a tight graph with diameter d ≥2. Recall that for each vertex x ofthe local graph(x)is strongly regular with parameters independent of x;we denote these parameters by(v,k, λ, µ). If c2 =µ +2,then eitherλ =0, µ =2,d ≥3and α=1,oris one of the following graphs:
(i) a Johnson graph J(2m,m),with m ≥2, (ii) a halved(2m)-cube,with m≥2,
(iii) a Cocktail Party graph Km×2,with m≥3,
(iv) the Gosset graph with intersection array{27,10,1; 1,10,27}.
Proof: Ifd =2 thenis a complete multipartite graphKm×nwithm≥3, andc2−µ = (m−2)n−(m−3)n=n=2 implies thatis a Cocktail Party graphKm×2withm≥3. So let us now assumed ≥3. Sinceis a tight graph, it is locally connected andad =0 by [10,
Theorem 12.6 and Theorem 11.7]. Nowµ =0, implies that the local graph is complete, and henceis complete as well, so we haveµ ≥1 andc2 =µ +2≥3. Hence,is one of the graphs in the list of Theorem 1.1 withad =0 and we are done.
The paper is organized in the following way. In Section 2 we introduce some local conditions that are satisfied by a 1-homogeneous graph having all theµ-graphs equal to the complete multipartite graph Kt×n. Then we establish some basic properties of graphs that satisfy these local conditions. The most important such property is that the intersection parameter αcan only betort−1. Letbe a graph that satisfies these local conditions. In Section 3 we study the smallest eigenvalue of the local graphs of. Ifα=t, then−nis the smallest eigenvalue of. Ifα=t−1, then eithern=2, orλ =0 andµ =2. This sets the stage for our classification of 1-homogeneous graphs withc2 =µ +2. In Section 4 we determine all such graphs that are additionally locally grid graphs or locally triangular graphs. In Section 5 we prove the main theorem.
2. Local regularity conditions
We establish some basic properties of graphs that satisfy certain local regularity conditions.
If a graph is regular with v vertices and valency k in which any two vertices at distance 2 have preciselyµ=µ() common neighbours, then it is calledco-edge-regular with parameters (v,k, µ), see [3, p. 3]. Letbe a distance-regular graph with diameter d. For vertices x and y of at distance i,1 ≤ i ≤ d, we define the sets Ci(x,y) = i−1(x)∩(y),Ai(x,y)=i(x)∩(y) and Bi(x,y) =i+1(x)∩(y),and say that has theCABj property, j≥1,when the partition
CABi(x,y)= {Ci(x,y),Ai(x,y),Bi(x,y)}
of the local graph ofyis equitable for each pair of verticesxandyofat distancei ≤ j. Since the graphwitha1 =0 is 1-homogeneous graph if and only if it has CABdproperty (see [11, Theorem 3.1]), we can now take a local approach to 1-homogeneous graphs.
We will start with a study of a distance-regular graphwith diameter at least 2 that is µ-locally the complete multipartite graphKt×n,n,t ∈ N, and for whicha2 = 0 and the intersection numberαexists withα≥1. Sinceα≤a1we have alsoa1 =0. The intersection numberαexists in a distance-regular graph witha2=0 when it has additionally the CAB2
property (αis equal to the number of neighbours that a vertex ofA2has inC2), therefore also for 1-homogeneous graphs. Certain examples of tight graphs areµ-locally the complete multipartite graphKt×n,n,t ∈N, cf. [10] and [12]. Ifis 1-homogeneous, thenc2=µ+1 if and only ifis a Terwilliger graph, i.e.,isµ-locallyKt. Such graphs withc2>1 have been classified in [11, Theorem 4.10].
It is quite natural to assumea2=0 in, since otherwise we have, by [3, Proposition 5.5.1]
and [3, Proposition 1.1.5], either
(a) a1=0, in which case any partition of a local graph ofis equitable, or (b) a1=0 andd =2, in which caseisK(t+1)×n.
Similarly, as in the case of Terwilliger 1-homogeneous graphs [11, Lemma 4.1], there are also only two possibilities forαin the present situation.
Lemma 2.1 Letbe a distance-regular graph with diameter at least2that isµ-locally the complete multipartite graph Kt×n,and for which a2 =0and the intersection number αexists withα≥1. Then the following holds.
(i) c2 = nt, each local graph of is µ-locally K(t−1)×n and co-edge-regular with parameters (v,k, µ), where v = k,k = a1, and µ = n(t −1). Moreover, αa2=c2(a1−µ).
(ii) Let x and y be vertices ofat distance2.Then for all z ∈ D12(x,y)the subgraph induced by(z)∩D11(x,y)is complete.
(iii) α∈ {t−1,t},i.e.,t−1≤α≤t,
(iv) is a Terwilliger graph(i.e.,c2=µ +1)if and only if n=1,and
(v) is locally connected if and only if t = 1 (in which case every local graph has diameter2).
Proof:
(i) Aµ-graph of is Kt×n, so it has c2 = nt vertices. Letx be a vertex of. Since has diameter at least 2, the local graph(x) is not a complete graph. Any two nonadjacent vertices of(x) haveµ =(t−1)ncommon neighbours in(x) and these common neighbours induceK(t−1)×n. Hence(x) is co-edge-regular with parameters (k,a1, µ). By a two way counting of the edges between D11(x,y) and D12(x,y), we findαa2=c2(a1−µ).
(ii) Suppose the opposite. Then|D11(x,y)∩(z)| ≥ 2 and there exist two nonadjacent verticesu, v∈ D11(x,y)∩(z). ThenD11(u, v)⊇ {x,y,z}and the subgraph induced byD11(u, v) is not complete multipartite, sinceyandzare in the same coclique asx and are adjacent.
(iii) We haveα ≤t by (ii). Letxandybe vertices ofat distance 2. Letz ∈ D21(x,y) and A=(z)∩D11(x,y). Supposeα≤t −2. Then there are two adjacent vertices u, v ∈ D11(x,y) such that the subgraph induced by {u} ∪ {v} ∪A is complete and
∂(u,z)=2=∂(v,z). Then the set(u)∩D11(v,z) contains A∪ {x}, which means thatα= |A| ≥ |A∪ {x}| =α+1. Contradiction! Henceα≥t−1.
(iv) and (v) Lett =1 andw1, w2 be nonadjacent vertices of the local graph(x). Then x∈D11(w1, w2) so∂(w1, w2)=2 and there is (t−1)nneighbours ofxin theµ-graph ofw1andw2and hence also in the local graph(x). Hence(x) has diameter 2. The rest follows now directly from (i).
We could relax the distance-regularity assumption on the graphin Lemma 2.1 to the requirement that the intersection numbersk,c2,a1anda2exist (see figure 2.1(a)).
Since the 1-homogeneous graphs that areµ-locallyKt×n, witht =1 have been classified in [16], we assume from now ont ≥2. Lemma 2.1 implies that we can calculatea2in terms
Figure 2.1. (a) The distance distribution corresponding to a vertex and the intersection numbersk,a1,c2and a2; (b) The distance distribution corresponding toyandz,∂(y,z) = 1. Then we have|D11(y,z)| = a1 and
|D12(y,z)| = |D12(y,z)| =b1.(c) The distance distribution corresponding toxandy,∂(x,y)=2. Then we have
|D11(x,y)| =c2and|D12(x,y)| = |D21(x,y)| =a2.
ofa1,nandt:
a2=
na1−(t−1)n2 ifα=t, t a1n
t−1−n2t ifα=t−1. (1)
Let us now assume additionally that the local graphs ofare strongly regular with parame- ters (v,k, λ, µ). We have already mentioned thatα≤a1impliesa1=0. In Lemma 2.1(i) we expressedv,k andµ in terms ofa1,nandt, therefore we can do the same forλ:
λ =a1−1+µ −µ(k−1) a1
=a1−1+n(t−1)−n(t−1)(k−1) a1
. (2)
Ifd =2, thenis strongly regular and 1-homogeneous.
3. Eigenvalues of local graphs
Letbe a distance-regular graph with diameter at least 2, that is locally strongly regular andµ-locally the complete multipartite graph Kt×n,t ≥ 2, for whicha2 = 0, and the intersection numberαexists withα≥1. We study the smallest eigenvalue of a local graph of.
Let x1, . . . ,xn be vertices of a graph. Then we denote the intersection (x1)∩ · · ·
∩(xn) by(x1, . . . ,xn) and the corresponding induced subgraph by(x1, . . . ,xn).
Lemma 3.1 Letbe a distance-regular graph with diameter at least 2that is locally strongly regular with parameters (v,k, λ, µ)and µ-locally the complete multipartite graph Kt×n,t ≥ 2,for which a2 = 0,and the intersection numberαexists withα ≥ 1.
For an edge xy of,the subgraph(x,y)is co-edge-regular with parameters(v ,k , µ ), where
v =k, k =λ, and µ =n(t−2),
for t ≥ 3 the subgraph(x,y)has diameter 2, and it contains an equitable partition π = {P1,P2}with quotient matrix
n(t−2) λ −n(t−2) α−1 λ −α+1
.
In particular,|P1| =n(t−1),|P2| =a1−n(t−1)and
(α−1)(a1−n(t−1))=(λ −(t−2)n)n(t−1). (3) Proof: The verification of co-edge-regularity is similar as in the case of Lemma 2.1(i).
Let z ∈ D12(x,y). By Lemma 2.1(iii) and the fact that the valency of(x,y) isλ, the partition
{(x)∩(y)∩(z), (x)∩(y)∩2(z)},
is an equitable partition of the graph (x,y) with the required quotient matrix, see Figure 2.1(b, c). The first set in the above partition hasµ =n(t −1) vertices, while the other one hasa2=k −µ =a1−n(t−1) vertices. We obtain (3) by a two way counting of edges that are connecting vertices from different parts of the above partition.
The relation (3) gives us
λ =1−n−α+n(t−1)+a1(α−1)
n(t−1) , (4)
hencen(t−1)|a1(α−1). The above relation and (2) imply that one can expresskin terms ofn,α,tanda1.
Theorem 3.2 Letbe a distance-regular graph with diameter at least2,that is locally strongly regular andµ-locally the complete multipartite graph Kt×n,for which a2 = 0, and the intersection number αexists withα = t ≥ 2. Then,for all vertices x of,the smallest eigenvalue of(x)equals−n.
Proof: Suppose that the parameters of the local graphs that are strongly regular are (v,k, λ, µ). It follows directly from the relation (3) andα = t that a1 −n(t −1) = (λ −(t −2)n)n. Now using thatn(t −1) = µ anda1 = k it follows thatk −µ = (λ −µ +n)n and hence −n is the negative eigenvalue of the local graph (x) with parameters (v,k, λ, µ).
Theorem 3.3 Letbe a distance-regular graph with diameter at least2,that is locally strongly regular with parameters (v,k, λ, µ)and µ-locally the complete multipartite
graph Kt×n,for which a2=0,and the intersection numberαexists withα=t−1≥2.
Then there exists a positive integer a such that−a−n is the smallest eigenvalue of every local graph and
n(λ −n(t−2))=a(t−2)(λ −n(t−3)+a). (5)
In particular,a(t−2)<n.
Proof: Fix a vertexxof. Letsbe the smallest eigenvalue of the local graph(x). Then µ −k =(λ −µ −s)s.
On the other hand,k =a1andµ =n(t−1) by Lemma 2.1(i), so by (3) andα=t−1, we have
(λ −µ +n)n(t−1)=(t−2)(λ −µ −s)(−s).
This means that−s>n,in particularsis negative. Seta:= −n−sin the above identity and we obtain (5). To show thatais integral, suppose the opposite. Then(x) is a conference graph with parameters (4µ+1,2µ, µ−1, µ), sok=4µ+1,a1=2µ andλ =µ −1.
Applying (4) we obtainn =t−1, sok=4(t−1)2+1,a1=b1=2(t−1)2,c2 =nt = (t−1)t, λ =t(t−2) andk2 =kb1/c2 =2(4t2−8t+5)(t −1)/t,which impliest|10, thus, byt ≥ 3,we havet =5 ort =10.Let y ∈ (x). Then, by|D21(x,y)| = b1 and
|D22(x,y)| =a1(b1−b1)/α=2(t−1)3,we obtain
k2−D22(x,y)−D12(x,y)= −2(t−1)(−5t2+8t−5+t3)
t <0,
which is impossible. Therefore,(x) is not a conference graph, and soais integral.
Supposea(t−2)≥n. Then, by (5), we obtain
λ −n(t−2)≥λ −n(t−3)+a, i.e., −n ≥a,
which is not possible sinceais a positive integer. Therefore, we havea(t−2)<n.
Note that the assumptionsα=t−1 andα≥1 implyt=α+1≥2.
Corollary 3.4 Letbe a distance-regular graph with diameter at least2,that is locally strongly regular with parameters (v,k, λ, µ) and µ-locally the Cocktail Party graph Kt×2,for which a2=0,and the intersection numberαexists withα=t−1. Thenα=1, λ =0andµ =2.
Proof: Supposeα >1, i.e.,t ≥3. By Theorem 3.3, we obtaina(t −2) <n =2,and thereforea=1 andt=3. This implies that every local graph inis strongly regular with parameters (57, 16, 5, 4). However, this is not possible, since for these parameters we do
not have integral eigenvalue multiplicities. Therefore,α=1,and sot =2.Henceµ =2 andλ =0 by Lemma 2.1(i) and relation (4).
Lemma 3.5 Letbe a distance-regular graph with diameter at least 2that is locally strongly regular with parameters (k,a1,0,2) and eigenvalues a1 > p > q. Then p is a nonnegative integer, not congruent 3 (mod 4), q = −p−2,a1 = (p +1)2 +1, k=1+a1(a1+1)/2and b1=a1(a1−1)/2.
Proof: The graphis not locally a conference graph, sinceλ =0=1=µ −1,so p is a nonnegative integer and we have
(p+1)2=
p+λ −µ 2
2
= (λ −µ)2
4 +(k −µ)=a1−1.
The multiplicities of the nontrivial eigenvalues are integral if and only if pis not congruent 3 (mod 4). The remaining relations are straightforward.
Remark 3.6
(i) For p = 0,1,2, i.e., a1 = 2,5,10, the local graphs of are respectively the quadrangle,the folded 5-cube with intersection array{5,4; 1,2}(also called the Cleb- sch graph),and the Gewirtz graph with intersection array{10,9; 1,2}. These are the only known strongly regular graphs withλ=0 andµ=2.
(ii) We are interested in the case,whenis additionallyµ-locallyKt×2,t ≥ 2,a2 =0 and the intersection numberα=1. Then,by Lemma 2.1(iii) and (i), Lemma 3.5 and the nonexistence of a strongly-regular graph with parameters (57,16,5,4),we have
t =2, c2 =4, a1>5, a2=4(a1−2), b2 =(a1−5)(a1−2)/2 and d ≥3.
Finally,if we additionally assume thatis 1-homogeneous,then we can apply [11, Algorithm 4.7] in order to obtain thatd =3 and thatis not locally Gewirtz,i.e., a1 =10.
Conjecture 3.7 There is no 1-homogeneous distance-regular graph with diameter at least 2,that is locally strongly regular with parameters (v,k,0,2),that has a2=0,the intersection numberα=1 and thatisµ-locallyKt×2,t≥2.
4. Locally grid and locally triangular graphs
Before we start to study locally grid and locally triangular graphs, we need to introduce some basic notions about codes. Letbe a graph with diameterd and the vertex setX. A
codeCinis a nonempty subset ofX. Then thedistance of a vertexx∈ XtoCand the covering radiusofCrespectively are
∂(x,C) :=min{∂(x,y)|y∈C} and t(C) :=max{∂(x,C)|x ∈X}.
LetPibe the set of vertices at distancei fromCandt =t(C). The codeCiscompletely regular when the partition {Pi | i = 0, . . . ,t} is equitable. This definition is due to Neumaier [14], who showed that in the case of distance-regular graphs it is equivalent to the original Delsarte’s definition, that the codeCis completely regular when for each vertex xofand for eachi ∈ {0,1, . . . ,t},the intersection number|C∩i(x)|depends only on
∂(x,C), see [6] or [3, p. 351]. A partitionπ of a graphgives rise to thequotient graph G/π with cells as vertices and two distinct cells Pi to Pj adjacent if there is an edge of joining some vertex ofPi to some vertex in Pj. An equitable partitionπ isuniformly regularif there are constantse01ande11such that the parameters of the equitable partition are
ci j=
e01 ifi = j,
e11 ifPi ∼Pj in/π.
The line graph ofKm,n, i.e., the graphKm×Kn, will be called the (m×n)-grid.
Proposition 4.1 Letbe a distance-regular graph with diameter at least2. Ifis locally the(m×n)-grid and c2=4,thenis the Johnson graph J(n+m,n),or m=n andis the folded Johnson graphJ¯(2m,m).
Proof: By [3, Theorem 9.1.3], the graphis the Johnson graph J(n+m,n), orm=n andis a quotient of the Johnson graphJ(2m,m). More precisely, in the latter case we can partition the vertex set ofJ(2m,m) into a uniform partitionπ:= {Pi|i =1, . . . ,(2mm)/2}, where|Pi| =2. By [3, Theorem 11.1.6], we obtain thatπ is completely regular, i.e. the sets Pi = {xi,yi}are completely regular with the same intersection numbers. Suppose
∂(xi,yi)=h <d =m.Then, bybh =0, there exists a neighbourvof xi that is at dist- anceh+1 fromyi. Therefore, each neighbour of a vertex inPi is at distanceh+1 from the other vertex ofPi. Henceh=1 (since otherwisech =0) anda1=0. Sincea1=2m−2, this is not possible, thus∂(xi,yi)=dfor everyi. It follows thatis the folded Johnson graph ¯J(2m,m).
The last part of the above proof was motivated by the proof of [13, Theorem 2.3.3].
The line graph of the complete graphKnis thetriangular graphT(n),i.e., the Johnson graph J(n,2). Note thatT(1) is an empty graph,T(2) is K1,T(3) is K3 andT(4) is the complete multipartite graphK2,2,2, i.e., the octahedron, andT(5) is the complement of the Petersen graph.
Proposition 4.2 Letbe a distance-regular graph with diameter d ≥3and let (i) be locally a triangular graph,
(ii) have the CABiproperty for some i ∈ {2, . . . ,d−1}.
Then for1 ≤ j ≤ i and for all vertices x and y at distance j the induced subgraph on Cj(x,y)is the triangular graph T(2j). Furthermore,if the distance between vertices x and y is i+1,then the subgraph induced on Ci+1(x,y)is a disjoint union of triangular graphs T(2i+2).
Proof: By [3, Proposition 4.3.9 and Lemma 4.3.10] (cf. [15, 20] and [21]), the condition (i) implies
• there exists an integernsuch that the graphis locallyT(n),
• is the halved graph of a bipartite graph with intersection numbersci() = i for i ≤3,and
• theµ-graphs inare isomorphic to the disjoint union of at mostn/4copies ofK2,2,2. Sok=n(n−1)/2 anda1=2(n−2). Sincec3()=3 anda2()=0, any 3-claw in determines a unique 3-cube by [3, Lemma 4.3.5(ii)]. Therefore, by [3, Proposition 4.3.6 and Corollary 4.3.7], then-cubeQncovers. More precisely, there exists a mapπ :V(Qn)→ V() that preserves distances≤3. It induces a mapπ :V(12Qn)→V(), that preserves adjacency (see figure 4.1). Let us denote byV the set of vertices of corresponding to the vertices of.
Let us definecm(u, v) :=cm()(u, v) for verticesu andv at distancemin and m =1,2, . . . ,diam(). Suppose we have shown for an integert, where 1≤ t <i,and for all j∈ {1, . . . ,t}that
(a) the subgraph ofinduced byCj(x,y) isT(2j) for allx,y∈V() with∂(x,y)= j, (b) cm(x,y)=mfor allm∈ {1, . . . ,2t+1},x ∈V andy ∈m(x).
Conditions (a) and (b) are certainly true fort =1 by the observation made at the beginning of this proof and sinceC1(x,y) contains only one vertex, which means that it inducesT(2).
Before continuing with the induction, we need to introduce some new notations. Letm be a positive integer,x ∈ V andy ∈ m(x). We say that the numbercmsemi-existsif cm(u, v)=cm(x,y) for allu ∈ V andv ∈m(u) andcm =cm(x,y). For vertices u andv at distancesin a graph X we denote byIX(u, v) theinterval graph, that is the
Figure 4.1. The halved graph ofQnis denoted by12Qnand called thehalvedn-cube.
subgraph of X induced by the set{w∈ V(X)|∂X(u, w)+∂X(v, w)=s}, i.e., the set of vertices that lie on a shortest path betweenuandv.
Letxbe a vertex ofandx the corresponding vertex of. Without loss of generality we may choose π to map the vector 0 to x. Since cm(Qn) = m = cm for all m ∈ {1,2, . . . ,2t +1}, by the induction assumption and since both graphs and Qn are bipartite, the mapπ preserves distances≤2t+1 when at least one of the vertices is from V , so also the mapπ preserves distances≤t, and the words of weightminQn are in 1-1 correspondence with the vertices at distancemfromx in.
Letz ∈ t+1(x) and letz be the corresponding vertex of. Thenz ∈ 2t+2(x) and sincec2t+1=2t+1 and is bipartite, the words of weight 2t+2 in the preimageπ −1(z) are mutually disjoint. Moreover, as 2t+1≥3, we have
ct+1=ct+1(x,z)= c2t+2(x,z)c2t+1
c2 = c2t+2(x,z)(2t+1)
2 ,
and thereforec2t+2semi-exists and it is equal to 2ct+1/(2t+1). The interval graphI(x,z) consist ofp:=c2t+2/(2t+2) copies of the (2t+2)-cubes sharing only the verticesx and z with each other.
Letbe the subgraph ofinduced by the setCt+1(x,z). Thenconsists of pdisjoint graphs and each of them is the halved graph of the second neighbourhood of the (2t+2)- cube. The halved graph of the second neighbourhood of thes-cube is the Johnson graph J(s,2), i.e., the triangular graphT(s). It follows that the graph is a disjoint union ofp copies of the triangular graphT(2t+2). Sincehas the CABt+1property andt<i ≤d−1 (so alsot+1 =d), the setCt+1(x,z) is a completely regular code with covering radius 2 in the triangular graphT(n). The latter graph can be considered as the line graph ofKn, and thepcopies ofT(2t+2) correspond topdistinguished disjoint (2t+2)-cliques ofKn, which do not cover all its vertices. Every edge ofKncorresponding to a vertex ofAt+1(x,z) connects a vertex from one of the distinguished (2t+2)-cliques with one of the remaining vertices of Kn, or, if p >1, it connects vertices from two distinct such (2t+2)-cliques.
However, the latter is not possible by the CABt+1property, thus we conclude that p =1 and soc2t+2=2t+2.
Now we will show thatc2t+2=2t+3. By the fact thatCt+1(x,z) is a completely regular code inT(n), it follows thatbt+1=(n−2t2−2). We have chosenxandzto be vertices of at distancet+1 andx,z as their corresponding vertices of at distance 2t+2,hence
(n−2t−2)(n−2t−3)
2 =bt+1 =bt+1(x,z)= 1 c2
y∈B2t+2(x,z)
b2t+3(x,y),
As is a bipartite graph withc2 =c2()=2, by [3, Proposition 1.9.1], it follows that ci(u, v)≥ifor all verticesu andv of at distancei. So, by|B2t+2(x,z)| =b2t+2 = n−c2t+2=n−(2t+2) andb2t+3(x,y)=n−c2t+3(x,y)≤n−(2t+3), we conclude b2t+3(x,y)=n−2t−3, which impliesc2t+3=2t+3. Now the proposition follows by induction.
For the convenience of the reader we give a proof of the following result.
Theorem 4.3(A.E. Brouwer) Letbe a bipartite distance-regular graph with diameter d ≥4and ci =i for i ≤d −1. Thenis a d-cube,a folded(2d)-cube or if d =4,the coset graph of the extended binary Golay code.
Proof: Ford =4 it follows from [4, Theorem 5.10 and Theorem 5.12] that either the valency equals 4, 8 or 24. For valency 24 it follows, by [2], thatis the coset graph of the binary Golay code. By [3, Theorem 11.1.6 and Corollary 4.3.7], there exists a completely regular code with the following distance partition (figure 4.2).
Figure 4.2. The distance partition of a certain completely regular code.
Ford ≥5,they were classified by van Tilborg, who showed|C| ≤2.The result follows now.
Theorem 4.4 Letbe a distance-regular graph with diameter d≥2. Then (i) is locally a triangular graph,and
(ii) is1-homogeneous
if and only ifis the halved n-cube,n≥ 4,oris the folded halved n-cube with n = 4m,m∈Nand m≥4,oris the halved coset graph of the extended binary Golay code.
Proof: Similarly as in the proof of Proposition 4.2, we start with the following:
(a) there exists an integernsuch that the graphis locallyT(n),
(b) is the halved graph of a bipartite graph with intersection numbersci()=i for i ≤3,and
(c) theµ-graphs inare isomorphic to the disjoint union of at mostn/4copies ofK2,2,2. Ifd≥3,then, by Proposition 4.2, for verticesx andyat distancei ∈ {1, . . . ,d−1}the subgraph induced by Ci(x,y) is the triangular graph T(2i), and for verticesx and yat distanced the subgraph induced byCd(x,y) is a disjoint union of the triangular graphs T(2d). Let us show that the same statement is true also whend = 2. We only need to check it fori =2.Letxandybe vertices ofat distance 2. Then we want to show that the subgraph induced byC2(x,y),i.e., theµ-graph ofx andyis a disjoint union of the triangular graphsT(4).SinceK2,2,2 is isomorphic toT(4),this statement coincides with the above property (c).
By the CABd property, this means that the subgraph induced onCd(x,y) is either one copy of the triangular graphT(2d),or the disjoint union of exactlyn/(2d) copies ofT(2d).
Therefore,is a distance-regular graph with intersection numbers ci =
2i
2 , bi =
n−2i
2 fori≤d−1, and cd ∈ 2d
2 , n 2d
2d
2 .
The first case can happen only when 2d ∈ {n,n−1}. But then|V()| =2n−1and, by [3, Corollary 4.3.8(ii)], the graphis the halvedn-cube,n ≥4.So we may assume that we are in the second case. This can only happen whend ≥3 and it is easy to see that 2d=d, whered is the diameter of.We are going to show is a distance-regular graph with intersection numbersci =ifori ≤d −1 andcd =n. As in the proof of Proposition 4.2, let V be the set of the vertices of of the corresponding to vertices ofand we have shown thatci(x,y)=ifori ≤d−1 andx ∈V ,y ∈V() at distancei.Furthermore, by assumptions we havecd =n.
Letx ∈V andy ∈V(). Then
|2i(x)| = n
2i , |2i(y)| ≤ n
2i ,
|2d(x)| =
n−1
2d−1 and |2i(y)| ≤
n−1 2d−1 , asci(u, v)≥ifor allu, v ∈V() at distancei.But
d i=0
|2i(x)| = d i=0
|2i(y)|
and thereforeci =i fori ≤ 2d −1 andc2d =n.Hence is a distance-regular graph with intersection numbersci=ifori ≤d −1 andcd =n, so is either then-cube, the folded 2n-cube or the coset graph of the extended binary Golay code by Theorem 4.3. As the halved folded (4m+2)-cube is not 1-homogeneous, the result follows now.
5. Proof of the main result
By Gardiner [7], in an antipodal distance-regular graphwith diameterDa vertexx, which is at distancei ≤ D/2from one vertex in an antipodal class, is at distanceD−i from all other vertices in this antipodal class, hence
D−i(x)=
{D(y)|y∈i(x)} fori=0,1, . . . ,D/2. (6) Ifis 1-homogeneous andx,yare its adjacent vertices, then it is not hard to conclude by (6) that, by taking antipodal quotient of, the cellsDdd−−ij(x,y) andDij(x,y) fold together for 0≤i,j ≤ d/2.However, it is even more effective to follow antipodal folding through CABipartitions ofand its antipodal quotient.
Theorem 5.1 Letbe an antipodal graph with diameter D ≥4and letbe its antipodal quotient graph with diameter d.Then for i≤d−1the graphhas the CABiproperty if and only ifhas the CABiproperty,and for D=2d the following are equivalent.
(i) The graphis1-homogeneous.
(ii) The graphhas the CABd property.
Figure 5.1. The CABdpartition in(left) and the CABdpartition in the antipodal quotient graph(right).
Moreover,ifis1-homogeneous and a1=0,thenis1-homogeneous if and only if D is even.
Proof: The first part of the statement and (i)⇔(ii) follow directly from the fact that a CABi partition of, the corresponding CABD−i partitions ofand the corresponding CABi partition ofare isomorphic by the covering projection fori =1, . . . ,d−1 (see figure 5.1).
Lety1, . . . ,yrbe the vertices of an antipodal class of, letxbe a vertex ofat distance dfromy1,and let ˆxand ˆybe the images of the covering projection corresponding toxand y1respectively. Consider the following partition
=Dd1−1(x,y1)∪ · · · ∪D1d−1(x,yr)∪
(x) r
i=1
Dd1−1(x,yi)
of the local graph ofx (see figure 5.2). If D = 2d,then the firstr sets have sizecd(), the last one has sizead(),and there are no edges betweenD1d−1(x,yi) andDd1−1(x,yj) wheni = j,which means that the partitions CABd(x,yi) fori =1, . . . ,r are equitable with the same parameters if and only if the partitionis equitable, in which casehas the
Figure 5.2. The partition corresponding to the distance distribution of the antipodal class{y1, . . . ,yr}in the case whenDis even (left) and the case whenDis odd (right). We have chosenrto be three. Inside this partition there is a partition of the neighbourhood of the vertexx.
following quotient matrix
g 0 0 · · · 0 a1−g 0 g 0 · · · 0 a1−g 0 0 g · · · 0 a1−g ... ... ... . .. ... ... 0 0 0 · · · g a1−g h h h · · · h a1−rh
(7)
for some integersgandh. If (i)–(ii) holds, theng=γd =a1−δd,h=αd =βd/(r−1) and the CABd partition of is equitable with the quotient matrix (rγαd δd
d a1−rα). Thus, we have shown that ifis 1-homogeneous andDis even, thenhas the CABdproperty, i.e., is 1-homogeneous.
Finally, let us suppose the antipodal quotient graph is 1-homogeneous, i.e., has the CABd property, and let (ga,, aa1−g
1−a) be the quotient matrix of the CABd( ˆx,y) partition inˆ . Suppose Dis odd. Then the local graph of ˆx is disconnected, (see figure 5.2 (right)), and we have g = a1 anda = 0. By [11, Proposition 2.2], the setCd( ˆy,x)() is inde-ˆ pendent in, which is not possible becausea1 = 0.Therefore, we have D = 2d by [3, Proposition 4.2.2].
Remark 5.2 The Foster graph is an antipodal distance-regular graph with diameter 4 and intersection array{6,4,2,1; 1,1,4,6}.It is locally disconnected, therefore it is not a tight graph in the sense of [10], and hence not 1-homogeneous (see [10, Theorem 11.7]).
However, its antipodal quotient is the complement of the triangular graph T(6) and it is 1-homogeneous. Thus, under the assumptions of the above result is not necessary 1- homogeneous whenis 1-homogeneous andD=2d.
Theorem 5.3 A graphis an 1-homogeneous graph with diameter at least2,that is µ-locally the complete multipartite graph Kt×2,t ≥2,and for which a2 =0and the inter- section numberαexists withα=t if and only ifis one of the following:
(i) a Johnson graph J(2m,m)with m≥3, (ii) a folded Johnson graphJ¯(4m,2m)with m≥3, (iii) a halved m-cube with m≥5,
(iv) a folded halved(4m)-cube with m ≥3,
(v) the Schl¨afli graph with intersection array{16,5; 1,8}, (vi) the Gosset graph with intersection array{27,10,1; 1,10,27}.
Proof: Letbe an 1-homogeneous graph with diameter at least 2 that isµ-locally the complete multipartite graphKt×2,t ≥2,and for whicha2=0 and the intersection number αexists withα=t.Letxbe a vertex of. Then the subgraph(x) is a connected strongly regular graph by [11, Theorem 3.1 and Proposition 2.1] and the smallest eigenvalue of(x) is−2 by Theorem 3.2. By Seidel’s classification [17], [3, Theorem 3.12.4], the local graph (x) is either
