There does not exist a distance-regular graph with intersection array \80, 54,12; 1, 6, 60\

DOI10.1007/S00373-019-02095-2MaRDI QIDQ2287750zbMATH OpenOpenAlexFDO

Authors Jack H. Koolen, Quaid Iqbal, Jongyook Park, Masood Ur Rehman

Publication date 21 January 2020

Published in Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

claw-boundDelsarte cliquesdistance regular-graphsgeometric distance-regular graphs

Mathematics Subject Classification ID

Distance in graphs (05C12) Association schemes, strongly regular graphs (05E30)

Abstract: In this paper we will show that there does not exist a distance-regular graph $Gamma$ with intersection array $80,54,12;1,6,60$. We first show that a local graph $Delta$ of $Gamma$ does not contain a coclique with 5 vertices, and then we prove that the graph $Gamma$ is geometric by showing that $Delta$ consists of 4 disjoint cliques with 20 vertices. Then we apply a result of Koolen and Bang to the graph $Gamma$, and we could obtain that there is no such a distance-regular graph.

Review text

The introduction of the paper is presented as review because it describes given work here very precisely. ``In this paper, we will show that there does not exists a distance-regular graph \(\Gamma \) with intersection array \(\left\{ 8,\ 54,\ 12;1,\ 6,\ 60\right\}\). In order to do so, we will first study the claw-bound that was introduced by Bose in the case of pseudo geometric strongly regular graphs [\textit{R. C. Bose}, Pac. J. Math. 13, 389--419 (1963; Zbl 0118.33903)]. We note that a similar bound for amply-regular graphs with an \(s\)-claw was shown by \textit{C. D. Godsil} [N. Z. J. Math. 22, No. 2, 31--38 (1993; Zbl 0793.05146)] and that \textit{J. H. Koolen} and \textit{J. Park} [Eur. J. Comb. 31, No. 8, 2064--2073 (2010; Zbl 1221.05117)] also studied the claw-bound for distance-regular graphs and they mentioned that three known examples of Terwilliger graphs with \(c_{2}\geq 2\) meet equality in the claw-bound. After that, \textit{A. L. Gavrilyuk} [Electron. J. Comb. 17, No. 1, Research Paper R125, 8 p. (2010; Zbl 1277.05173)] showed that if an amply-regular Terwilliger graph with \(c\geq 2\) attains equality in the claw-bound, then the graph is one of the known Terwillinger graphs. Next, we will show that for a given vertex \(x\) of \(\Gamma ,\) the subgraph \(\Delta\) induced on the neighbors of \(x\) does not contain a coclique of size 5. From the claw-bound, it is easy to see that \(\Delta\) does not contain a coclique of size 6. One may think that non-existence of coclique of size 5 follows from the result of Gavrilyuk [loc. cit., Theorem 4.2], but it is not true because his result works if for any non-adjacent two distinct vertices in \(\Delta,\) there exists a coclique of size 5 containing them. So, we need to give a proof to show that \(\Delta\) does not contain a coclique of size 5 without using the result of Gavrilyuk . Also, we remark that Gavrilyuk [loc. cit., Theorem 4.2] missed to state that the graph is Terwilliger. Finally, we will show that \(\Delta\) consists of 4 disjoint cliques of size 20. This shows that the graph \(\Gamma\) is geometric and then a result by \textit{J. H. Koolen} and \textit{S. Bang} [J. Comb. Theory, Ser. B 100, No. 6, 573--584 (2010; Zbl 1203.05043)] finishes the proof.

Recommendations

• The Koolen-Park boundary and distance-regular graphs without \(m\)-claws
• Distance-regular graph with the intersection array \(\{45, 30, 7; 1, 2, 27\}\) does not exist
• ON THE NON-EXISTENCE OF CERTAIN DISTANCE-REULAR GRAPHS
• Distance-regular graphs with intersection arrays \(\{52, 35, 16; 1, 4, 28\}\) and \(\{69, 48, 24; 1, 4, 46\}\) do not exist
• The nonexistence of a distance-regular graph with intersection array \(\{22,16,5;1,2,20\}\)

Cites work

• Distance-regular graphs
• scientific article; zbMATH DE number 43547 (Why is no real title available?)
• scientific article; zbMATH DE number 563236 (Why is no real title available?)
• On distance-regular graphs with smallest eigenvalue at least \(- m\)
• On the Koolen-Park inequality and Terwilliger graphs
• Shilla distance-regular graphs
• Strongly regular graphs, partial geometries and partially balanced designs

Cited in

(13)

• A distance regular graph with intersection array \((21,16,8;1,4,14)\) does not exist
• Augmenting the Delsarte bound: a forbidden interval for the order of maximal cliques in strongly regular graphs
• Distance-regular Terwilliger graphs with intersection arrays \(\{50,42,1;1,2,50\}\) and \(\{50,42,9;1,2,42\}\) do not exist
• Distance-regular graphs with intersection array \(\{69,56,10;1,14,60\}\), \(\{74,54,15;1,9,60\}\) and \(\{119,100,15;1,20,105\}\) do not exist
• Distance-regular graphs with intersection arrays \(\{42,30,12;1,6,28\}\) and \(\{60,45,8;1,12,50\}\) do not exist
• The Koolen-Park boundary and distance-regular graphs without \(m\)-claws
• On distance-regular graphs without 4-claws
• ON THE NON-EXISTENCE OF CERTAIN DISTANCE-REULAR GRAPHS
• Distance-regular graphs with intersection arrays \(\{52, 35, 16; 1, 4, 28\}\) and \(\{69, 48, 24; 1, 4, 46\}\) do not exist
• The nonexistence of a distance-regular graph with intersection array \(\{75,64,22,1;1,2,64,75\}\)
• Distance-regular graph with the intersection array \(\{45, 30, 7; 1, 2, 27\}\) does not exist
• Distance-regular graph with intersection array \(\{143,108,27;1,12,117\}\) does not exist
• Non-existence of two infinite families of strongly regular graphs

This page was built for publication: There does not exist a distance-regular graph with intersection array \(\{80, 54,12; 1, 6, 60\}\)

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