Neumaier graphs with few eigenvalues

DOI10.1007/S10623-021-00856-WMaRDI QIDQ2168070zbMATH OpenOpenAlexFDO

Authors Aida Abiad, Bart De Bruyn, Jozefien D'haeseleer, Jack H. Koolen

Publication date 31 August 2022

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

edge-regular graphNeumaier graphregular cliquestrongly regular graph

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Association schemes, strongly regular graphs (05E30)

Abstract: A Neumaier graph is a non-complete edge-regular graph containing a regular clique. In this paper we give some sufficient and necessary conditions for a Neumaier graph to be strongly regular. Further we show that there does not exist Neumaier graphs with exactly four distinct eigenvalues. We also determine the Neumaier graphs with smallest eigenvalue -2.

Review text

A Neumaier graph is a non-complete edge-regular graph containing a regular clique; in this paper, the authors characterize Neumaier graphs as having exactly three distinct eigenvalues, that is, strongly regular Neumaier graphs. In Section 2, the authors give multiple characterizations of these graphs, extending some results in [\textit{A. Neumaier}, Lond. Math. Soc. Lect. Note Ser. 49, 244--259 (1981; Zbl 0466.05026)] They give a characterization in terms of cliques, which is combinatorial; one in terms of the eigenvalues of the graph; one using Hoffman's ratio bound; one using \(t\)-walk regularity; and finally, one using the smallest eigenvalue being \(-2\). In Section 3, they show some feasibility conditions of Neumaier graphs with four distinct eigenvalues and use them to prove that there does not exist strictly Neumaier graphs with exactly four distinct eigenvalues.

Recommendations

• The smallest strictly Neumaier graph and its generalisations
• An infinite class of Neumaier graphs and non-existence results
• Edge-regular graphs with regular cliques
• A generalization of a theorem of Neumaier
• Regular graphs with four eigenvalues

Cites work

• A characterization of distance-regular graphs with diameter three
• An introduction to the theory of graph spectra
• Another construction of edge-regular graphs with regular cliques
• Cayley-Deza graphs with fewer than 60 vertices
• Edge-regular graphs with regular cliques
• Geometric aspects of 2-walk-regular graphs
• scientific article; zbMATH DE number 3730160 (Why is no real title available?)
• scientific article; zbMATH DE number 43547 (Why is no real title available?)
• scientific article; zbMATH DE number 740754 (Why is no real title available?)
• scientific article; zbMATH DE number 2232233 (Why is no real title available?)
• Intriguing sets of vertices of regular graphs
• On \(k\)-walk-regular graphs
• Regular graphs with four eigenvalues
• The smallest strictly Neumaier graph and its generalisations

Cited in

(7)

• The smallest strictly Neumaier graph and its generalisations
• A general construction of strictly Neumaier graphs and a related switching
• Sesqui-regular graphs with fixed smallest eigenvalue
• On the Existence of Small Strictly Neumaier Graphs
• Vertex-transitive Neumaier graphs
• Hoffman colorability of (strongly) regular graphs
• Edge-regular graphs with fixed smallest eigenvalue with an application to Neumaier graphs

This page was built for publication: Neumaier graphs with few eigenvalues

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