On highly regular strongly regular graphs (Q2065709): Difference between revisions

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.