On highly regular strongly regular graphs

DOI10.5802/ALCO.183MaRDI QIDQ2065709zbMATH OpenOpenAlexFDO

Authors Christian Pech

Publication date 12 January 2022

Published in Algebraic Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

\(t\)-isospectral \(t\)-vertex condition rank 3 graph strongly regular graphs

Mathematics Subject Classification ID

Association schemes, strongly regular graphs (05E30) Generalized quadrangles and generalized polygons in finite geometry (51E12)

Abstract: In this paper we unify several existing regularity conditions for graphs, including strong regularity,

k

-isoregularity, and the

t

-vertex condition. We develop an algebraic composition/decomposition theory of regularity conditions. Using our theoretical results we show that a family of non rank 3 graphs known to satisfy the

7

-vertex condition fulfills an even stronger condition,

(3, 7)

-regularity (the notion is defined in the text). Derived from this family we obtain a new infinite family of non rank

3

strongly regular graphs satisfying the

6

-vertex condition. This strengthens and generalizes previous results by Reichard.

Review text

A graph \(\Gamma=(V,E)\) is called strongly regular with parameters \((v,k,\lambda,\mu)\) if it has \(v\) vertices, is \(k\)-regular, any two adjacent vertices in \(V\) have exactly \(\lambda\) common neighbors, and any two non-adjacent and distinct vertices in \(V\) have precisely \(\mu\) common neighbors. The study of strongly regular graphs is an important part of algebraic combinatorics (see [\textit{A. E. Brouwer} and \textit{H. Van Maldeghem}, Strongly regular graphs. Cambridge: Cambridge University Press (2022; Zbl 1498.05001)]). If \(G\) is a permutation group acting on set \(V\), its rank is the number of orbits (also called orbitals) of \(G\) on \(V\times V\). If \(G\) is transitive of rank \(3\) and the orbitals \(D=\{(v,v):v\in V\}\), \(E\), and \(F\) are symmetric, then \((V,E)\) and \((V,F)\) form a pair of complementary strongly regular graphs. Not every strongly regular graph arises in this way. A graph \(\Gamma=(V,E)\) satisfies the \(t\)-vertex condition if for all the triples \((T,x_0,y_0)\) consisting of a \(t\)-vertex graph \(T\) and two distinct vertices \(x_0\), \(y_0\) of \(T\), and all pairs of distinct vertices \(x,y\in V\) (with \(x\) adjacent to \(y\) if and only if \(x_0\) is adjacent to \(y_0\) in \(T\)), the number of isomorphic copies of \(T\) in \(\Gamma\), where the isomorphism sends \(x_0\) to \(x\) and \(y_0\) to \(y\), does not depend on the choices of \(x\) and \(y\). A rank \(3\) graph satisfies the \(t\)-vertex condition for every \(t\). A graph satisfies the \(3\)-vertex condition if and only if it is strongly regular or complete or edgeless. A result of \textit{C. C. Sims} [Math. Z. 103, 276--281 (1968; Zbl 0259.20003)] gives a necessary and sufficient condition for a strongly regular graph to satisfy the \(4\)-vertex condition (see Brouwer and Van Maldeghem (loc. cit.]). There is an open conjecture of H. Klin (see [\textit{I. A. Faradžev} et al., Math. Appl., Sov. Ser. 84, 1--152 (1994; Zbl 0795.05073)]) stating that there exists \(t_0\) such that any graph satisfying the \(t_0\)-vertex condition must be rank 3 (see [Faradžev et al., loc. cit.]). It is known that if such \(t_0\) exists, then \(t_0\geq 8\). A graph \(\Gamma=(V,E)\) is \(t\)-uple regular or \(t\)-isoregular if for any subset of vertices \(S\) of size at most \(t\), the size of \(S^{\perp}=\{x: x\text{ adjacent to } s,\forall s\in S\}\) depends on the isomorphism type of \(S\) only. A graph is \(1\)-isoregular if and only if it is regular. A graph is \(2\)-isoregular if and only if it is strongly regular, complete or edgeless. In this paper, the author studies and compares the \(t\)-vertex and the \(t\)-isoregular properties to other conditions such as \(T\)-regularity and \((m,n)\)-regularity which are introduced in this paper.

Recommendations

Cites work

Cited in

(22)

Describes a project that uses

Uses Software

This page was built for publication: On highly regular strongly regular graphs

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