Strongly regular graphs with the $7$-vertex condition

Abstract

The $t$-vertex condition, for an integer $t\ge 2$, was introduced by Hestenes and Higman (SIAM Am Math Soc Proc 4:41–160, 1971) providing a combinatorial invariant defined on edges and non-edges of a graph. Finite rank 3 graphs satisfy the condition for all values of $t$. Moreover, a long-standing conjecture of Klin asserts the existence of an integer $t_0$ such that a graph satisfies the $t_0$-vertex condition if and only if it is a rank 3 graph. We present the first infinite family of non-rank 3 strongly regular graphs satisfying the $7$-vertex condition. This implies that the Klin parameter $t_0$ is at least 8. The examples are the point graphs of a certain family of generalized quadrangles.

1 Introduction

Strongly regular graphs (see Sect. 2) occur naturally as rank 3 representations of finite permutation groups, and there are many other examples. Whereas in principle all finite rank 3 graphs are known (see, e.g., [25, 30]), the more general problem of classifying the finite strongly regular graphs appears completely hopeless. Hence, it is natural to consider properties of graphs which are satisfied by the rank 3 graphs and also some other, but not all, strongly regular graphs.

Special attention is given to a family of properties which allow to distinguish quite rare sequences and sporadic examples of graphs, and which correlate with exceptional geometrical features of strongly regular graphs.

Hestenes and Higman [19] introduced a family of such properties of this type called the $t$-vertex condition for integers $t\ge 2$. This condition is described in detail in Sect. 4. For a graph $\varGamma$ and integer $t\ge 3$, the $t$-vertex condition leads to a combinatorial invariant on pairs of distinct vertices of $\varGamma$; if this invariant is constant on the edges, we say that $\varGamma$ satisfies the $t$-vertex condition on edges, and similarly for non-edges.

The $2$-vertex condition is equivalent to regularity of graphs, while the $3$-vertex condition is equivalent to strong regularity. Also for any $t\ge 3$, if a graph satisfies the $t$-vertex condition then it also satisfies the $(t-1)$-vertex condition (see Sect. 4). In a rank 3 graph, all edges and all non-edges are equivalent under the automorphism group, and hence cannot be distinguished combinatorially, therefore these graphs satisfy the $t$-vertex condition for any $t$.

There is a long-standing conjecture by Klin [15] that there exists a number $t_0$ such that the only graphs satisfying the $t_0$-vertex condition are the rank 3 graphs. Since for any fixed $t$ the $t$-vertex condition can be checked in polynomial time (see Theorem 4), a proof of Klin’s conjecture would have the remarkable consequence that rank 3 graphs can be recognized combinatorially in polynomial time.

Hence it is interesting to consider graphs which are not rank 3 graphs, but which satisfy the $t$-vertex condition for large $t$.

For $t=2$ it is easy to find regular graphs which are not strongly regular, and hence not rank 3 graphs, a small example being the cycle $C_6$. The smallest strongly regular graph ($t=3$) which is not a rank 3 graph is the well-known Shrikhande graph on 16 vertices, which can be constructed from a Latin square of order $4$.

In 1971, Higman [20] gave the first examples for $t=4$. He showed that the point graphs of generalized quadrangles (see Sect. 5) satisfy the 4-vertex condition. The smallest example of a generalized quadrangle that does not admit a rank 3 group is the unique $GQ(5,3)$ on 96 points.

In the late 1980s, Ivanov [21] constructed the first graph with the 5-vertex condition that was not a rank $3$ graph. It has the parameters of a Latin square graph $L_8(16)$ on $256$ vertices. Its first and second sub-constituents (subgraphs induced by the neighbors and non-neighbors, respectively, of a given vertex) of orders $120$ and $135$ are strongly regular and satisfy the 4-vertex condition. The graph on 135 vertices was the first example known to satisfy the $4$-vertex condition and have an intransitive automorphism group. Later, Brouwer, Ivanov, and Klin [4] generalized the construction above, obtaining an infinite series of graphs of order $4^k$ with the 4-vertex condition. These graphs in fact satisfy the 5-vertex condition as was shown by the author in [37].

For more historical details we refer to Sect. 9.

Here, we will once more look at the point graphs of generalized quadrangles. First, we strengthen the original result by Higman:

Theorem 1

The point graph of a generalized quadrangle satisfies the $5$-vertex condition.

Second, we show that a much stronger result can be obtained for generalized quadrangles of order $(s,s^2)$.

Theorem 2

For an integer $s$, the point graph of a generalized quadrangle of order $(s,s^2)$ satisfies the $7$-vertex condition.

Both results are best possible in the sense that there is a generalized quadrangle of order $(5,3)$ which does not satisfy the 6-vertex condition, and there is a generalized quadrangle of order $(5,25)$ which does not satisfy the 8-vertex condition.

This provides us with an infinite family of graphs with intransitive automorphism groups which satisfy the 7-vertex condition.

Corollary 1

The constant $t_0$ in Klin’s Conjecture is at least 8.

All necessary main concepts are introduced in Sects. 2–5. The proofs of the two main theorems appear in Sects. 6 and 7. In Sect. 8 we discuss further possibilities to improve our Corollary 6.

Finally, Sect. 9 stands a bit alone. Here we return to the discussion of the history of the considered research line in a quite wide historical perspective.

2 Strongly regular graphs

All graphs considered in this text are finite and simple, i.e., undirected and without loops or multiple edges. Thus, a graph $\varGamma$ is a finite set $V=V(\varGamma )$ of vertices together with a binary symmetric and anti-reflexive relation referred to as adjacency. We call $v=|V|$ the order of $\varGamma$.

If $x$ and $y$ are distinct vertices of $\varGamma$, we write $x\sim y$ if they are adjacent, and say that $y$ is a neighbor of $x$. Otherwise, we call $y$ a non-neighbor of $x$, and write $x\not \sim y$.

Let $\varGamma (x)=\{y\in V|x\sim y\}$ denote the set of neighbors of $x$ in $\varGamma$. The valency of $x$ is defined as $\mathrm val (x)=|\varGamma (x)|$.

Definition 1

(Regular graph) A graph $\varGamma$ is regular if there is a number $k$ such that $\mathrm val (x)=k$ for all vertices $x\in V$. In this case, $k$ is called the valency of $\varGamma$.

Definition 2

(Strongly regular graph) A graph $\varGamma$ is strongly regular if there are numbers $k$, $\lambda$, $\mu$ such that

• $\varGamma$ is regular of valency $k$;

• any two adjacent vertices of $\varGamma$ have exactly $\lambda$ common neighbors, i.e., $|\varGamma (x)\cap \varGamma (y)|=\lambda$ whenever $x\sim y$.

• any two distinct, non-adjacent vertices of $\varGamma$ have exactly $\mu$ common neighbors, i.e., $|\varGamma (x)\cap \varGamma (y)|=\mu$ whenever $x\not \sim y$.

In this case, the numbers $(v,k,\lambda ,\mu )$ are called the parameters of $\varGamma$, where $v=|V|$ is its order.

We refer to Sect. 9 for a brief discussion of numerical restrictions on putative parameters of $\varGamma$.

3 Isoregular graphs

There are several ways to generalize the concept of strong regularity. One of them is the $t$-vertex condition, which we will discuss in Sect. 4. Another one is isoregularity.

Let $\varGamma =(V,E)$ be a graph, and let $S\subset V$ be a set of vertices. We define the valency of $S$ as

$$\begin{aligned} \mathrm val (S) = \left| \bigcap _{x\in S}\varGamma (x)\right| , \end{aligned}$$

i.e., the number of vertices adjacent to all elements of $S$. Note that this generalizes the notion of valency since for any vertex $x$, $\mathrm val \left( \left\{ x\right\} \right) = \mathrm val (x)$.

Definition 3

Let $\varGamma =(V,E)$ be a graph, and $k\ge 1$ be an integer. Suppose that for each set $S$ of at most $k$ vertices, the valency of $S$ depends only on the isomorphism class of the subgraph of $\varGamma$ induced by $S$. Then $\varGamma$ is called $k$ -isoregular.

Proposition 1

For $k > 1$, $k$-isoregularity implies $(k-1)$-isoregularity.

Proof

Follows directly from the definition. If the valency of any set $S$ of up to $k$ elements depends only on the isomorphism class of the induced subgraph, this holds in particular for all sets of up to $k-1$ elements.

Proposition 2

A graph $\varGamma$ is $k$-isoregular if and only if its complement $\overline{\varGamma }$ is $k$-isoregular.

Proof

Let $\varGamma$ be $k$-isoregular. Let $S$ be a set of $k$ vertices in $\varGamma$. Since we have $i$-isoregularity for $1\le i \le k$, we know the valency of every subset of $S$. Using the Principle of Inclusion and Exclusion, we can determine the number of vertices not adjacent to any element of $S$, i.e., the valency of $S$ in the complement of $\varGamma$. Since the calculation depends only on the isomorphism class of the subgraph of $\varGamma$ induced by $S$, and since this holds for any $k$-subset $S$, $\overline{\varGamma }$ is $k$-isoregular.

Proposition 3

A graph $\varGamma$ is $1$-isoregular if and only if it is regular. It is $2$-isoregular if and only if it is strongly regular.

Proof

Since there is only one isomorphism class of graphs of order 1, and since the valency of a singleton $\{x\}$ is the same as the valency of the vertex $x$, a graph is $1$-isoregular if and only if each vertex has the same valency, in other words, if and only if the graph is regular.

There are two isomorphism classes of graphs of order $2$, namely, edges and non-edges. A graph is $2$-isoregular if and only if it is $1$-isoregular, i.e., regular, and if the number of common neighbors of two distinct vertices $x$ and $y$ depends only on whether $x$ is adjacent to $y$. However, this is exactly the definition of strong regularity.

For a graph $\varGamma$, a vertex $x$, and an integer $i$, we define the $i$ -th subconstituent $\varGamma _i(x)$ as the subgraph of $\varGamma$ induced by all vertices at distance $i$ from $x$.

Proposition 4

For a strongly regular graph $\varGamma$, the following are equivalent:

• $\varGamma$ is $3$-isoregular.

• The subconstituents $\varGamma _i(x)$, $i=1,2$, are strongly regular, with parameters which do not depend on the choice of $x$.

Proof

There are four isomorphism classes of graphs of order $3$, determined uniquely by the number of edges they contain. We will denote these classes by $\varDelta _i$, where $0\le i\le 3$ is the number of edges.

Let $\varGamma$ be a $3$-isoregular graph. By Proposition 1, it is $2$-isoregular, and hence strongly regular, with parameters $(v,k,\lambda ,\mu )$.

Let $x$ be a vertex of $\varGamma$, and let $\varGamma _1=\varGamma (x)$, the subgraph induced by the neighbors of $x$. Then $\varGamma _1$ is a regular graph of order $k$ and valency $\lambda$. Let $y$ and $z$ be vertices of $\varGamma _1$. Then the common neighbors of $y$ and $z$ in $\varGamma _1$ are exactly the common neighbors of $x,y,z$ in $\varGamma$.

If $y\sim z$, then $x,y,z$ induce a complete graph $\varDelta _3$ in $\varGamma$. Hence, $y$ and $z$ have $\mathrm val (\varDelta _3)$ neighbors in $\varGamma _1$. Similarly, if $y\not \sim z$, $x,y,z$ induce the graph $\varDelta _2$ in $\varGamma$. Thus $y$ and $z$ have $\mathrm val (\varDelta _2)$ neighbors in $\varGamma _1$. So we get that $\varGamma _1$ is strongly regular, with parameters

$$\begin{aligned} v_1&= k\\ k_1&= \lambda \\ \lambda _1&= \mathrm val (\varDelta _3)\\ \mu _1&= \mathrm val (\varDelta _2)). \end{aligned}$$

We get strong regularity for the second subconstituents by working with the complement of $\varGamma$. More precisely, if $\varGamma$ is 3-isoregular, then so is the complement $\bar{\varGamma }$, by Proposition 2. Then, by the argument above, the first subconstituent of $\bar{\varGamma }$ is strongly regular; however, this is precisely the complement of the second subconstituent of $\varGamma$.

Conversely, assume that $\varGamma$ is a strongly regular graph with parameters $(v,k,\lambda ,\mu )$, such that the subconstituents $\varGamma _i(x)$, $i=1,2$, are strongly regular with parameters $(v_i,k_i, \lambda _i, \mu _i)$. By assumption, $\varGamma$ is $2$-isoregular, hence we only need to check the graphs $\varDelta _i$ of order $3$. Clearly, in $\varGamma$ we have $\mathrm val (\varDelta _3)=\lambda _1$, and $\mathrm val (\varDelta _2) = \mu _1$.

Let $x,y,z$ be pairwise non-adjacent vertices in $\varGamma$. Then $y$ and $z$ have $\mu$ common neighbors in $\varGamma$; of these, $\mu _2$ are not neighbors of $x$. Hence we get that $\mathrm val (\varDelta _0) = \mu -\mu _2$.

Similarly, if $y\sim z$, and both are non-adjacent to $x$, they have $\lambda$ neighbors in $\varGamma$, and $\lambda _2$ neighbors in $\varGamma _2$. Hence, $\mathrm val (\varDelta _1)=\lambda -\lambda _2$.

Altogether, we get that $\varGamma$ is $3$-isoregular.

4 The $t$-vertex condition

Here, we discuss another way of generalizing strong regularity. Let $\varGamma$ be a graph of order $v$. Let $T$ be a graph of order $t$, with two distinguished vertices $x_0$ and $y_0$. We will denote such a triple $(T, x_0, y_0)$ as a graph type. We call $x_0$ and $y_0$ fixed vertices, the other vertices of $T$ will be called additional vertices.

Let $x,y$ be vertices of $\varGamma$, and let $\varDelta$ be an induced subgraph of $\varGamma$ containing both $x$ and $y$. We say $\varDelta$ is of type $T$ (with respect to $x$ and $y$) if there is an isomorphism $\phi :T\rightarrow \varDelta$ which maps $x_0$ to $x$ and $y_0$ to $y$.

Definition 4

Let $\varGamma$ be a graph, and let $t\ge 2$ be an integer. Suppose that for any graph type $(T, x_0, y_0)$ of order at most $t$, and for any pair of vertices $(x,y)$ of $\varGamma$, the number of subgraphs of $\varGamma$ which are of type $T$ w.r.t. $x$ and $y$ depends only on whether $x$ and $y$ are equal, adjacent, or non-adjacent. Then $\varGamma$ is said to satisfy the $t$ -vertex condition.

In other words, $\varGamma$ satisfies the $t$-vertex condition if we cannot distinguish its edges (vertices, non-edges) by considering subgraphs of order up to $t$.

Proposition 5

For $t>2$, the $t$-vertex condition implies the $(t-1)$-vertex condition.

Proof

Follows directly from the definition.

Proposition 6

A graph $\varGamma$ satisfies the $2$-vertex condition if and only if it is regular. It satisfies the $3$-vertex condition if and only if it is strongly regular.

Proposition 7

A rank 3 graph of order $v$ satisfies the $v$-vertex condition.

Proof

In a rank 3 graph, the automorphism group acts transitively on vertices, (directed) edges and non-edges. Hence we cannot distinguish edges (resp. non-edges) on a combinatorial level.

For growing $t$, the number of graph types to check increases very quickly. However, it turns out that many of these checks are redundant.

Theorem 3

([37]) Let $\varGamma$ be a $k$-isoregular graph which satisfies the $(t-1)$-vertex condition. In order to check that $\varGamma$ satisfies the $t$-vertex condition it suffices to consider graph types in which each additional vertex has valency at least $k+1$.

The idea behind the proof is the following: Suppose that $\varGamma$ does not satisfy the $t$-vertex condition. Then there is a graph type $(T, x, y)$ of order $t$ such that the number of induced subgraphs of this type does depend on the choice of $x$ and $y$. We may assume that $T$ is maximal w.r.t. this property, in other words, for any graph type $T^{\prime }$ where $T^{\prime }$ properly contains $T$, the numbers are invariant. If $T$ contains a vertex $z$ (other than $x$ and $y$) of valency at most $k$, we can delete $z$ and use the $(t-1)$ vertex condition to count the resulting graph type; after that we use the $k$-isoregularity to recover the number of graphs of type $(T,x,y)$. This contradicts the choice of $T$.

In fact, we will be using the following reformulation of Theorem 3:

Corollary 2

Let $\varGamma$ be a graph which is $k$-isoregular, and which satisfies the $(t-1)$-vertex condition, but not the $t$-vertex condition. Then there is a graph type $(T,x,y)$ of order $t$ such that all vertices other than $x$ and $y$ have valency at least $k+1$, and such that the number of graphs of type $(T,x,y)$ depends on the choice of $x$ and $y$ in $\varGamma$.

Finally, we present a complexity result related to the $t$-vertex condition:

Theorem 4

For a fixed integer $t$ and a graph $\varGamma$ of order $n$, the $t$-vertex condition can be checked in time polynomial in $n$.

Proof

We may assume that $t\ge 3$, and that the $(t-1)$-vertex condition has already been checked.

Fix a graph type $T=(\varDelta , z_1, z_2)$ of order $t$ and two vertices $z_1^{\prime }, z_2^{\prime }$ of $\varGamma$. Suppose that either both $(z_1,z_2)$ is an edge in $\varDelta$ and $(z_1^{\prime },z_2^{\prime })$ is an edge in $\varGamma$, or both pairs are non-edges in their respective graphs. Arbitrarily label the remaining vertices in $\varDelta$ by $z_3, \ldots , z_t$.

Now we consider all sequences $(z_3^{\prime }, \ldots , z_t^{\prime })$ of distinct vertices in $\varGamma$; there are fewer than $n^{t-2}$ of them. For each sequence we may consider the labeled subgraph induced by the $z_i^{\prime }$, $1\le i\le t$. We can check in time proportional to $t^2$ whether $\phi :z_i\mapsto z_i^{\prime }$ is a graph isomorphism. Hence, in time $O(n^{t-2}t^2)$ we can count the graphs of type $T$ with respect to the given vertices $z_1^{\prime }$ and $z_2^{\prime }$.

There are fewer than $n^2$ possible pairs $(z_1^{\prime }, z_2^{\prime })$ of vertices. Repeating the count for all of them gives us the numbers of graphs of type $T$ for all these pairs in time $O(n^{t-2}\cdot n^2)= O(n^t)$, since $t$ is constant. Since there are only finitely many graph types of order $t$, this proves the theorem.

5 Generalized quadrangles

Definition 5

Let $P$ be a finite set of points. Let $L$ be a set of distinguished subsets of $P$, called lines. Suppose there are integers $s$ and $t$ such that

• any two lines intersect in at most one point;

• each line contains exactly $s+1$ points;

• each point is contained in exactly $t+1$ lines.

Then $(P,L)$ is a partial linear space of order $(s,t)$.

We use the traditional geometric language: Two points are collinear if they lie on a common line; two lines are concurrent if they intersect.

Given a partial linear space, we can define a graph as follows:

Definition 6

Let $(P,L)$ be a partial linear space. Let $\varGamma$ be the graph with vertex set $P$, two points being adjacent if they are collinear. Then $\varGamma$ is called the point graph of $(P,L)$.

Generalized quadrangles are partial linear spaces which satisfy one additional regularity property.

Definition 7

Let $(P,L)$ be a partial linear space of order $(s,t)$. Suppose that for each line $l$ and each point $P\notin l$, there is exactly one point on $l$ collinear to $P$. Then $(P,L)$ is a generalized quadrangle of order $(s,t)$, or a $GQ(s,t)$ for short.

Below we survey a few classical results about generalized quadrangles.

Theorem 5

The point graph of a $GQ(s,t)$ is strongly regular, with parameters

$$\begin{aligned} v&= (s+1)(st+1)\\ k&= (s-1)t\\ \lambda&= s-1\\ \mu&= t+1 \end{aligned}$$

We now look at subgraphs of the point graphs of generalized quadrangles.

Theorem 6

(Cameron [10]) The point graph of a generalized quadrangle does not contain $K_4-e$ as an induced subgraph. Here, $K_4-e$ denotes the graph obtained by removing one edge from the complete graph on 4 vertices.

Definition 8

A triad in a $GQ(s,t)$ is a triple $\{x,y,z\}$ of pairwise non-collinear points. A center of a triad is a point collinear to all three points of the triad.

Theorem 7

(see [35]) For a generalized quadrangle of order $(s,t)$, we have $s^2\ge t$. Equality holds if and only if each triad has exactly $s+1$ centers.

Corollary 3

The point graph of a generalized quadrangle of order $(s,s^2)$ is $3$-isoregular.

Proof

The isomorphism class of a graph of order $3$ is uniquely determined by the number of edges. By Theorem 7, each graph with 0 edges has $s+1$ common neighbors. By Theorem 6, each graph with 2 edges has no common neighbors.

If the graph has 1 edge, two of the points are connected by a line. The third point has exactly one neighbor on this line, which is the unique common neighbor of all three points. Thus, a graph with 1 edge has one common neighbor.

If the graph has 3 edges, it is complete, and hence contained in a line. The common neighbors of the three points are the remaining $s-2$ points on this line.

6 Proof of Theorem 1

6.1 Goals and strategy

In this section we prove Theorem 1, which states that the point graph of a generalized quadrangle satisfies the $5$-vertex condition. For generalized quadrangles of order $(s,s^2)$, this has been previously shown by Pasini (unpublished [33]). Although the proof presented here is independent, the result in [33] showed that generalized quadrangles yield a class of strongly regular graphs which should be further investigated. Also, some of the techniques used by Pasini helped to obtain the result presented here.

By Theorem 3 it suffices to count order $5$ graphs (with fixed vertices $x$, $y$) in which the three additional vertices $a$, $b$, and $c$ each have valency of at least 3. In other words, if $x,y$ are the fixed vertices, and $a,b,c$ the additional vertices, we need to consider the graphs in which each of $a,b,c$ is non-adjacent to at most one vertex.

If we take the complements of these graphs, we get that the valency of each of $a,b,c$ is at most 1. If we discard a possible edge $(x,y)$, that implies that the size of the graph, i.e., the number of its edges, is at most 3. Thus, we use the following strategy:

• (1) Enumerate all graphs of order 5 and size $i=0,1,2,3$ (Sect. 6.2);

• (2) Discard those graphs which cannot appear as subgraphs of generalized quadrangles (Sect. 6.3);

• (3) For the few remaining graph types, check that their numbers do not depend on the choice of the edge or non-edge $(x,y)$ (Sect. 6.4).

6.2 Graph types relevant to the 5-vertex condition

We start by determining all graph types which need to be considered in order to check whether a given graph satisfies the 5-vertex condition. As stated above, the size of the complements of these graph types is bounded by 3, in other words, the complements contain at most 3 edges.

In order to be sure not to miss anything, we will completely enumerate these complements. In the following we enumerate the relevant graphs up to isomorphism under the group $S(\{x,y\})\times S(\{a,b,c\})$ of order 12, counting also the cardinalities of the related isomorphism classes. We will not consider the set $\{x,y\}$ as a possible edge. This leaves $\left( {\begin{array}{c}5\\ 2\end{array}}\right) -1 = 9$ possible edges.

We denote graphs by a list of its edges.

• Graphs of size 0

  The empty graph is uniquely determined by its size.

• Graphs of size 1

  • (a) $\{x,a\}$, $Aut = \left<(b,c)\right>, |Aut| = 2$, length of orbit: 6.

  • (b) $\{a,b\}$, $Aut = \left<(a,b), (x,y)\right>, |Aut| = 4$, length of orbit: 3.

  This accounts for $6+3=9=\left( {\begin{array}{c}9\\ 1\end{array}}\right)$ graphs.

• Graphs of size 2

  • (a) $\{x,a\},\{x,b\}$, $Aut = \left<(a,b)\right>, |Aut| = 2$, length of orbit: 6.

  • (b) $\{x,a\},\{y,b\}$, $Aut = \left<(a,b)(x,y)\right>, |Aut|=2$, length of orbit: 6.

  • (c) $\{x,a\},\{b,c\}$, $Aut = \left<(b,c)\right>, |Aut|=2$, length of orbit: 6.

  • (d) $\{x,a\},\{y,a\}$, $Aut = \left<(x,y),(b,c)\right>, |Aut|=4$, length of orbit: 3.

  • (e) $\{x,a\},\{a,b\}$, $Aut = \left<e\right>, |Aut|=1$, length of orbit: 12.

  • (f) $\{a,b\},\{b,c\}$, $Aut = \left<(a,c),(x,y)\right>, |Aut|=4$, length of orbit: 3.

  This accounts for $6+6+3+12+6+3=36=\left( {\begin{array}{c}9\\ 2\end{array}}\right)$ graphs.

• Graphs of size 3

  • (a) $\{x,a\},\{x,b\},\{x,c\}$, $Aut=S(\{a,b,c\}$, $|Aut| = 6$, length of orbit: 2.

  • (b) $\{x,a\},\{x,b\},\{y,c\}$, $Aut=\left<(a,b)\right>$, $|Aut| = 2$, length of orbit: 6.

  • (c) $\{x,a\},\{x,b\},\{y,a\}$, $Aut=\left<e\right>$, $|Aut| = 1$, length of orbit: 12.

  • (d) $\{x,a\},\{x,b\},\{a,b\}$, $Aut=\left<(a,b)\right>$, $|Aut| = 2$, length of orbit: 6.

  • (e) $\{x,a\},\{x,b\},\{a,c\}$, $Aut=\left<e\right>$, $|Aut| = 1$, length of orbit: 12.

  • (f) $\{x,a\},\{y,a\},\{a,b\}$, $Aut=\left<(x,y)\right>$, $|Aut| = 2$, length of orbit: 6.

  • (g) $\{x,a\},\{y,a\},\{b,c\}$, $Aut=\left<(x,y),(b,c)\right>$, $|Aut| = 4$, length of orbit: 3.

  • (h) $\{x,a\},\{y,b\},\{a,b\}$, $Aut=\left<(a,b)(x,y)\right>$, $|Aut| = 2$, length of orbit: 6.

  • (i) $\{x,a\},\{y,b\},\{a,c\}$, $Aut=\left<e\right>$, $|Aut| = 1$, length of orbit: 12.

  • (j) $\{x,a\},\{a,b\},\{a,c\}$, $Aut=\left<(b,c)\right>$, $|Aut| = 2$, length of orbit: 6.

  • (k) $\{x,a\},\{a,b\},\{b,c\}$, $Aut=\left<e\right>$, $|Aut| = 1$, length of orbit: 12.

  • (l) $\{a,b\},\{a,c\},\{b,c\}$, $Aut=\left<(x,y),(a,b),(a,b,c)\right>$, $|Aut| = 12$, length of orbit: 1.

  This accounts for $2 +4\cdot 12 + 5\cdot 6 + 3+1 = 84 = \left( {\begin{array}{c}9\\ 3\end{array}}\right)$ graphs. This check sum confirms that our enumeration is complete.

The following graphs can be discarded because one of the additional vertices has valency greater than 1: 2.d–f, 3.c–l

This can be summarized as follows (recall that above we enumerated the complements of the relevant graphs):

Theorem 8

If a graph $\varGamma$ satisfies the 4-vertex condition, then to check the 5-vertex condition it is sufficient to count the graphs of the eight types given in Fig. 1. Here, a dashed line indicates an optional edge connecting the fixed vertices.

Fig. 1

Types to check for 5-vertex condition

6.3 Easily discarded cases

We now proceed to apply the results obtained above to point graphs of generalized quadrangles. In this case, most of these graph types can be discarded since they contain a subgraph $K_4-e$, which cannot happen in a generalized quadrangle (see Theorem 6).

Lemma 9

In a generalized quadrangle, the following graph types do not appear: 1a, 1b, 2b, 2c, 3b.

Proof

In the pictures of Fig. 1, we denote the fixed vertices left to right by $x,y$, and the additional vertices left to right by $a,b,c$. For each of the graph types, we note a set of vertices which induces a $K_4-e$:

1a::

$x,a,b,c$

1b::

$x,a,b,c$

2b::

$x,a,b,c$

2c::

$y,a,b,c$

3b::

$y,a,b,c$

So these types do not occur, independent of whether $x$ and $y$ are adjacent.

6.4 The remaining cases

This leaves us to check the following types: 0, 2a, 3a.

We will now show that the numbers for these subgraphs are uniquely determined by the axioms of generalized quadrangles. We will arrange these verifications in three lemmas, one for each type.

Lemma 10

The number of graphs of type 0 w.r.t. $x$ and $y$ is $\left( {\begin{array}{c}s-1\\ 3\end{array}}\right)$ if $x\sim y$, 0 otherwise.

Proof

If $x\not \sim y$, then the graph contains a $K_4-e$. Otherwise, each additional vertex is adjacent to both $x$ and $y$ and hence lies on the line connecting them. Each set of three points on this line yields a graph of type 0.

Lemma 11

The number of graphs of type 2a is 0 if $x\sim y$. Otherwise, it is $(t+1)\left( {\begin{array}{c}s-1\\ 2\end{array}}\right)$.

Proof

If $x\sim y$, then $\{x,y,b,c\}$ induces a $K_4-e$. Let $x\not \sim y$. The points $\{y,a,b,c\}$ form a clique, hence lie on a line. Thus to find such a graph, we choose a line $l$ through $y$, with $t+1$ possibilities. The point $c$ is the unique neighbor of $x$ on $l$; for $a$ and $b$ we can choose any two of the remaining points on $l$.

Lemma 12

The number of graphs of type 3a is $t\left( {\begin{array}{c}s\\ 3\end{array}}\right)$ if $x\sim y$, $(t+1) \left( {\begin{array}{c}s-1\\ 3\end{array}}\right)$ otherwise.

Proof

The vertices $\{y,a,b,c\}$ form a clique, hence are collinear. If $x\sim y$, we can choose any line through $y$ but not through $x$; there are $t$ such lines. We need to choose 3 other points on this line; this gives us $\left( {\begin{array}{c}s\\ 3\end{array}}\right)$ choices.

If $x\not \sim y$, then we can choose any line through $y$ ($t+1$ possibilities) and then choose any three points on that line that are not adjacent to $x$, giving $\left( {\begin{array}{c}s-1\\ 3\end{array}}\right)$ choices.

We see that for all the graph types we have to check, the numbers do not depend on the particular choice of $x$ and $y$. Together with Theorem 3, this proves Theorem 1.

7 Proof of Theorem 2

7.1 Goals and preliminaries

For the remainder of the text, we concentrate on point graphs of generalized quadrangles of order $(s, s^2)$. Thus, let $s$ be fixed, and let $\varGamma$ be the point graph of such a generalized quadrangle.

Suppose that $\varGamma$ does not satisfy the $t$-vertex condition for some value of $t$, and let $t_1$ be minimal w.r.t. this property. Then $\varGamma$ satisfies the $(t_1-1)$-vertex condition by assumption.

Thus there is a graph type $(T, x_0, y_0)$ of order $t_1$ such that the number of graphs of type $T$ with respect to $x$ and $y$ does depend on the choice of $x$ and $y$. We may further assume that such $T$ is of maximal size, i.e., adding an edge to $T$, if possible, leads to a graph type such that the corresponding number does not depend on the choice of the fixed vertices.

We will try to find a lower bound on $t_1$; this will yield the result that $\varGamma$ satisfies the $(t_1-1)$-vertex condition.

First, let us collect some properties of $T$.

Proposition 8

We may assume that the valency of any additional vertex in $T$ is at least 4.

Proof

Since $\varGamma$ is 3-isoregular by Corollary 3, this follows from Corollary 2.

Lemma 13

$T$ does not contain an induced subgraph isomorphic to $K_4-e$.

Proof

Follows from Theorem 6 and the fact that $T$ is an induced subgraph of $\varGamma$.

Proposition 9

Let $X$ be the set of vertices adjacent to both $x$ and $y$ in $T$. If $x\sim y$, then the subgraph induced by $X$ is complete. If $x\not \sim y$, then the subgraph induced by $X$ is empty.

Proof

Let $w$ and $z$ be two distinct vertices both adjacent to each of $x$ and $y$. If exactly one of $(x,y), (w,z)$ is an edge in $T$, then these four vertices induce a graph isomorphic to $K_4-e$, contradicting the lemma above.

Let $S=V\setminus \{x,y\}$, where $V$ is the vertex set of the graph $T$ and $x$ and $y$ are the fixed vertices of $T$, see Fig. 2. Denote by $T[S]$ the subgraph of $T$ induced on the set $S$. Below, we collect information about $T[S]$.

• $T[S]$ has order $t_1-2$;

• $T[S]$ has minimal valency at least 2;

• The vertices of valency 2 in $S$ induce either a complete graph or an empty graph.

• For any maximal clique $C$ in $S$ and any vertex $z$ not in $C$, $z$ has at most one neighbor in $C$.

Fig. 2

The graphs $S$ and $T$

We now look at the possible subgraphs induced by $S$. In Sect. 7.2, we look at the case that $S$ induces a complete graph. In Sect. 7.3, we consider the other case.

7.2 $S$ is complete

We first consider the case that $S$ induces a complete graph in $T$. In this case, we can determine the number of graphs of type $T$, independent of the size of $S$.

Theorem 9

Let $\varGamma$ be the point graph of a $GQ(s, s^2)$. Let $(T,x_0, y_0)$ be a graph type of arbitrary size $t_1$, such that the additional vertices induce a complete graph $S$ in $T$. Then the number of graphs of type $(T, x_0, y_0)$ with respect to vertices $x$ and $y$ does not depend on the choice of $x$ and $y$ in $\varGamma$.

Proof

If $T[S]$ is a complete graph, then $S$ is contained in a line, say $l$. Either $x\in l$ and thus is collinear to all $t_1-2$ points in $S$, or it has at most one neighbor in $S$. The same holds for $y$. Let $d_x=|T(x)\cap S|$ be the number of neighbors of $x$ in $S$, and similar $d_y=|T(y)\cap S|$. We have that $d_x, d_y\in \{0,1,t_1-2\}$, and without loss of generality we may assume that $d_x\ge d_y$. We get six possibilities for the pair $(d_x, d_y)$, and in each case we can determine the number of graphs of type $T$ with respect to any pair $(x,y)$ of distinct vertices in $\varGamma$.

• $(d_x, d_y) = (t_1-2,t_1-2)$:

  

  In this case, both $x$ and $y$ are contained in $l$; in particular, $x\sim y$. Thus there are $\left( {\begin{array}{c}s-1\\ |S|\end{array}}\right)$ choices for the additional vertices.

• $(d_x, d_y) =(t_1-2, 1)$: Here, $x\in l$, $y\notin l$, and the unique neighbor $z$ of $y$ on $l$ lies in $S$. We have to distinguish the cases $x=z$ and $x\ne z$.

  

  If $x\sim y$, we can choose any line $l$ through $x$ but not through $y$, which gives $s^2$ possibilities. Then we need to choose a subset $S\subseteq l\setminus \{x\}$. Hence, altogether there are $s^2\left( {\begin{array}{c}s\\ t_1-2\end{array}}\right)$ such graphs.

  

  If $x\ne z$, then $x\not \sim y$. In order to find such a graph, we have to first choose the line $l$ through $x$, which gives $s^2+1$ possibilities. The point $z\in l$ is uniquely determined by $y$, and we need to choose the $t_1-3$ remaining vertices of $S$ on $l$. Altogether, there are $(s^2+1)\left( {\begin{array}{c}s-1\\ t_1-3\end{array}}\right)$ such graphs.

• $(d_x, d_y) =(t_1-2,0)$: Here, $x\in l$, and the unique neighbor $z$ of $y$ on $l$ does not lie in $S$. In particular, $x\not \sim y$.

  

  We can choose any line $l$ through $x$, and then a subset $S\subseteq l$ avoiding both $x$ and the unique neighbor of $y$ on $l$. Thus, the total number of such graphs is $(s^2+1)\left( {\begin{array}{c}s-1\\ t_1-2\end{array}}\right)$.

• $(d_x, d_y) =(1,1)$: Neither $x$ nor $y$ lie on $l$, and their unique neighbors $z_x$ and $z_y$ lie in $S$. We need to distinguish four cases, depending on whether or not $x\sim y$, and whether or not $z_x,z_y$ are equal.

  • $x\not \sim y$, $z_x\ne z_y$:

    

    Choose any line $l_1$ through $x$ ($s^2+1$ possibilities). On $l_1$ we take any other point $z_x$ which is not adjacent to $y$ ($s-1$ possibilities). Through $z_x$ we take any line $l\ne l_1$ ($s^2$ choices). On $l$, $z_x$ and $z_y$ are fixed, so we have to choose $|S|-2$ additional points. Thus the total number of such graphs is

    $$\begin{aligned} s^2(s^2+1)(s-1)\left( {\begin{array}{c}s-1\\ |S|-2\end{array}}\right) . \end{aligned}$$

  • $x\sim y$, $z_x\ne z_y$:

    

    Take any line $l_1$ through $x$ which does not contain $y$ ($s^2$ choices). Choose $z_x\ne x$ on $l_1$ ($s$ choices). By construction, $z_x\not \sim y$. Take any line $l\ne l_1$ through $z_x$ ($s^2$ choices); this determines $z_y$. Again, we need to choose the remaining $|S|-2$ points on $l$. The total number is

    $$\begin{aligned} s^5\left( {\begin{array}{c}s-1\\ |S|-2\end{array}}\right) . \end{aligned}$$

  • $x\not \sim y$, $z_x= z_y$:

    

    We take any common neighbor $z$ of $x$ and $y$ ($\mu$ choices). Through $z$ there are $s^2-1$ lines $l$ which do not contain $x$ or $y$. On $l$, we need to choose $|S|-1$ additional points. Hence, we get a total number of

    $$\begin{aligned} \mu (s^2-1)\left( {\begin{array}{c}s\\ |S|-1\end{array}}\right) . \end{aligned}$$

  • $x\sim y$, $z_x= z_y$:

    

    (The vertical line is a line of the geometry as well.) Here, the points $x$, $y$, and $z_x$ are pairwise adjacent, hence they are collinear. Let $l_1$ be the line through $x$ and $y$. We can choose any third point $z_x$ on $l_1$ ($s-1$ possibilities) and any line $l\ne l_1$ through $z_x$ ($s^2$ possibilities). Finally, we need to take $|S|-1$ additional points on $l$. The total number is

    $$\begin{aligned} s^2(s-1)\left( {\begin{array}{c}s\\ |S|-1\end{array}}\right) . \end{aligned}$$

• $(d_x, d_y) =(1,0)$: Again, we distinguish the cases $x\sim y$ and $x\not \sim y$.

  

  If $x\not \sim y$, we can take any line $l_1$ through $x$, and choose $x\ne z_x\not \sim y$. Through $z_x$ we take any line $l\ne l_1$, and on $l$ we need $|S|-1$ additional points, avoiding the neighbor of $y$. The total number of choices is

  $$\begin{aligned} (s^2+1)(s-1)s^2\left( {\begin{array}{c}s-1\\ |S|-1\end{array}}\right) . \end{aligned}$$

  

  If $x\sim y$, we choose $x\in l_x \not \ni y$. On $l_x$ we take any point $z_x\ne x$. Through $z_x$ we take any line $l\ne l_x$, and on $l$ we need $|S|-1$ more points, none of which is adjacent to $y$. The total number is

  $$\begin{aligned} s^2\cdot s \cdot s^2\left( {\begin{array}{c}s-1\\ |S|-1\end{array}}\right) . \end{aligned}$$

• $(d_x, d_y) =(0,0)$:

  

  If $x\not \sim y$, we can divide all lines in the GQ into three different parts. There are $2(s^2+1)$ lines which pass through either $x$ and $y$. On each of the remaining lines, both $x$ and $y$ have one common neighbor each. Let $L_1$ be the set of lines where these neighbors coincide, and $L_2$ the set of lines where the neighbors are distinct.

  Now $x$ and $y$ have $\mu$ common neighbors. Through each such neighbor there are $s^2-1$ lines which do not pass through either $x$ or $y$. All these lines are distinct, since otherwise, $x$ would have two neighbors on one line. Hence, we get that $|L_1|=\mu (s^2-1)$, and thus $|L_2|=l-|L_1|-2(s^2+1)$, where $l$ is the total number of lines.

  In order to obtain a graph depicted above, we take any line from $L_1\cup L_2$. On this line, we need to choose $|S|$ points avoiding the neighbors of $x$ and $y$. Thus, the total number of such graphs is

  $$\begin{aligned} |L_1|\left( {\begin{array}{c}s\\ |S|\end{array}}\right) + |L_2|\left( {\begin{array}{c}s-1\\ |S|\end{array}}\right) . \end{aligned}$$

  

  If $x\sim y$, we distinguish four types of lines: The line $l_0$ connecting $x$ and $y$; the set $L_1$ of lines intersecting $l_0$ in either $x$ or $y$; the set $L_2$ of lines intersecting $l_0$ in other points; and finally the set $L_3$ of lines skew to $l_0$.

  Clearly, $|L_1|=2s^2$. There are $s-1$ additional points on $l_0$; through each of them, there are $s^2$ lines distinct from $l_0$. All these lines are distinct, since otherwise, two lines would intersect in more than one point. Hence we get that $|L_2|=s^2(s-1)$, and hence, $|L_3|=l-1-|L_1| - |L_2|$.

  Now, by a similar reasoning as above, we get that the total number of graphs is

  $$\begin{aligned} |L_2|\left( {\begin{array}{c}s\\ |S|\end{array}}\right) + |L_3|\left( {\begin{array}{c}s-1\\ |S|\end{array}}\right) . \end{aligned}$$

This completes the proof.

7.3 $T[S]$ is not complete

Recall that $S$ is a set of $t_1-2$ vertices in the graph $T$ of order $t_1$.

Proposition 10

$T[S]$ does not contain a clique of size $t_1-3$.

Proof

If $S$ contains only one point $z$ not contained in a maximal clique $C$, then $z$ has to have two neighbors in $C$, which is a contradiction.

Proposition 11

$T[S]$ does not contain a clique of size $t_1-4$.

Proof

Suppose that $T[S]$ contains such a clique $C^{\prime }$, and two more vertices, $w$ and $z$. By the condition on the minimal valency of additional vertices, $w$ and $z$ are adjacent, and both have exactly one neighbor in $C^{\prime }$. Moreover, in $T$, they are both adjacent to each of $x$ and $y$, forcing $x\sim y$. Thus, in $T$, we have two cliques, $C^{\prime }$ of size $t_1-4$, and $C=\{x,y,w,z\}$ of size 4.

Let $l$ be the line in the generalized quadrangle containing $C$, and let $l^{\prime }$ be the line containing $C^{\prime }$. Both are uniquely determined. Denote the unique neighbors of $x,y,w,z$ on $l^{\prime }$ by $x^{\prime }, y^{\prime }, w^{\prime }, z^{\prime }$ respectively.

If $w^{\prime }=z^{\prime }$, then $l$ and $l^{\prime }$ intersect, and $x^{\prime }=y^{\prime }=w^{\prime }\in C^{\prime }$. In this case, we can count the graphs as follows: We select $w$ and $z$ on the line connecting $x$ and $y$. The intersection point $x^{\prime }$ has to lie on $l\setminus C$, which gives $s-3$ choices. There are $s^2$ other lines through $x^{\prime }$; we choose one of them and then select $t_1-5$ additional points on this line. Altogether, we get $\left( {\begin{array}{c}s-1\\ 2\end{array}}\right) (s-3) s^2 \left( {\begin{array}{c}s\\ t_1-5\end{array}}\right)$ such graphs.

If $w^{\prime }\ne z^{\prime }$, then $l$ and $l^{\prime }$ do not intersect, and hence $x^{\prime },y^{\prime },w^{\prime },z^{\prime }$ are all distinct. We choose the points $w$ and $z$ on $l$, and a line $l^{\prime }$ not intersecting $l$. The points $w^{\prime }$ and $z^{\prime }$ are uniquely determined; we can choose the remaining points according to whether or not $x$ and $y$ have neighbors in $C^{\prime }$. In each case, we can count easily how many graphs we obtain.

Thus, the number of graphs of type $T$ with respect to $x$ and $y$ does not depend on the choice of $x$ and $y$, which is a contradiction to the choice of $T$.

Collecting what we have so far, we get:

Corollary 4

$T[S]$ is a graph of order $t_1-2$ of minimal valency at least $2$ not containing a $t_1-4$ clique.

Corollary 5

$t_1\ge 7$.

Proof

By the minimal valency condition, $S$ contains an edge, i.e., a 2-clique. Thus $t_1-4>2$.

We now consider how many vertices in $T[S]$ can have valency $2$.

Proposition 12

If $x\sim y$, then there are at most three vertices in $T[S]$ of valency $2$.

Proof

In this case, the vertices of valency $2$ induce a complete graph by Proposition 9.

Proposition 13

If $x\not \sim y$, then there are at least two vertices with valency at least $3$.

Proof

In this case, the vertices of valency 2 induce an empty graph by Proposition 9. Each one has to have two neighbors, which necessarily have a valency greater than $2$.

Proposition 14

Let $x\not \sim y$. Let $z$ be a vertex of valency 3 in $T[S]$. Then $z$ can be adjacent to at most one vertex of valency 2.

Proof

Let $z$ be a vertex of valency 3. In $T$ it has to be adjacent to at least one of $x$ and $y$; let us assume that $z\sim x$. Let $v$ and $w$ be two vertices of valency 2 adjacent to $z$; this implies $v\not \sim w$. Both $v$ and $w$ have to be adjacent to $x$, which implies that $\{x,z,v,w\}$ induces a $K_4-e$.

Proposition 15

The case $t_1=7$ is impossible.

Proof

Assume that $t_1=7$, i.e., $T[S]$ has $t_1-2=5$ vertices. Then $T[S]$ does not contain a 3-clique. Let $z$ be a vertex with maximal valency in $S$. Then $z$ has at least 3 neighbors. These neighbors must be mutually non-adjacent to avoid a 3-clique. Since they have valency at least 2, they are all adjacent to one additional vertex. Since this accounts for 5 vertices, there are no additional vertices or edges in $S$.

However, now $z$ has valency 3, and it is adjacent to three non-adjacent vertices of valency 2, which is a contradiction.

Thus we have proved Theorem 2.

Corollary 6

The constant $t_0$ in Klin’s Conjecture is at least 8.

Proof

There are generalized quadrangles of order $(s,s^2)$ for some prime powers $s\ge 5$ with intransitive automorphism groups, see [34].

8 Towards the 8-vertex condition

For the 8-vertex condition, we have to consider a 6-vertex graph $S$ satisfying all the conditions stated in the previous section. A computer search has been performed, and the result is that there are 5 different graphs to consider: The complete bipartite graphs $K_{3,3}$ and $K_{4,2}$; the graph $K_{3,3}-e$ obtained by removing an edge from the complete bipartite graph; the triangular prism $K_3\circ K_2$, and the graph obtained from the prism by removing one edge from the prism which is not contained in a 3-clique. These graphs are shown in Fig. 3.

Fig. 3

Graphs relevant to the 8-vertex condition

It can be shown that the number of graphs of the types related to the prism can be determined in a generalized quadrangle of order $(s,s^2)$. However, for the bipartite graph types this is not the case:

Proposition 16

There is a $GQ(5,25)$ whose point graph does not satisfy the $8$-vertex condition.

This result was obtained via computer search using known generalized quadrangles. The quadrangle in question is obtained using the set of matrices

$$\begin{aligned} \left\{ \left( \begin{matrix} t&{}3t^2\\ 0&{}3t^3 \end{matrix} \right) \vert t\in GF(5)\right\} , \end{aligned}$$

see [35] and [34] for details of this construction. Its automorphism group has several orbits on edges, which can be distinguished by counting complete bipartite graphs $K_{4,4}$ containing a given edge.

9 Discussion

In this section we consider a number of topics which are naturally related to the main part of the paper but which were not immediately required for our presentation.

Nevertheless, we believe that a wider picture may be helpful for the reader. Also credits should be given to many other researchers who were dealing with the $t$-vertex condition, either explicitly or implicitly.

It is also worth mentioning that a first draft of the result given above appeared in the authors thesis [38], prepared at the University of Delaware.

9.1 More about strongly regular graphs

The classical concept of a strongly regular graph (SRG) goes back to the investigations of Bose in relation to the design of statistical experiments. For more than two decades it was considered in terms of partially balanced incomplete block designs, while the term itself was coined in [3].

There are a number of necessary conditions for the parameters $(v, k, \lambda , \mu )$ of a putative SRG, which are formulated by means of standard (or slightly more sophisticated) tools from spectral graph theory (cf. [6]) and which are called feasibility conditions.

There are many known infinite classes and series of SRG’s, in particular those coming from finite permutation groups and finite geometries.

There is a continuous interest to know all SRG’s (up to isomorphism) for a given feasible parameter set. A lot of such information is accumulated on the home page of Andries Brouwer [5].

On the other hand there exist so-called prolific constructions of SRG’s (in the sense of [9]); this usually means that for a given infinite series of feasible parameter sets the number of SRG’s grows exponentially. Techniques to present such prolific constructions were suggested by Wallis and developed quite essentially by Fon-Der-Flaass and Muzychuk, see [31].

The discovery of prolific constructions put a final dot in the understanding of the fact that the full classification of SRG’s is a hopeless problem.

One who is interested in “nice” SRG’s is forced to rigorously formulate additional requirements to the considered objects, using suitable group-theoretical or combinatorial language.

9.2 $k$-isoregular graphs

The concept of a $k$-isoregular graph has two independent origins, both related to the investigation of rank 3 permutation groups. The first origin is the Ph.D. thesis of Buczak (1980), fulfilled at Oxford. The main results of this thesis were briefly mentioned in Sect. 8 of [8], while the text itself was not available to Klin and his colleagues for three decades.

The other origin is the paper [17], where all absolutely homogeneous graphs were classified and first steps were taken towards the investigation of $k$-homogeneous graphs for $k\ge 2$; note that 2-homogeneous graphs are exactly rank 3 graphs.

It should be mentioned that the investigation of absolutely homogeneous graphs was an attractive goal for many other researchers. More or less at the same time the full classification was suggested in publications by Cherlin, Gardiner, Enomoto, Ronse, Sheehan and others, see, e.g., the detailed bibliography in the book [12].

It was Gol’fand who first realized that the concept of a $k$-homogeneous graph may be approximated in purely combinatorial terms by $k$-isoregular graphs. In particular, absolutely isoregular graphs coincide with the absolutely homogeneous graphs, and the proof of this fact may be achieved without any use of group-theoretical arguments. An outline of the proof (due to Gol’fand) is presented in the Sect. 4.3 of [28].

In fact, the history of this proof is just a small visible part of the related drama of ideas. Around 1979–1980 Gol’fand prepared a manuscript with the claim that each 5-isoregular graph (5-regular in the original terminology) is absolutely regular. Unfortunately a fatal mistake (discovered by Klin) appeared on the very last page of this detailed text. However, all previous results in this ingenious text were correct, thus the real claim obtained by Gol’fand was the description of two putative infinite classes of parameter sets for 4-isoregular graphs. One class corresponds to absolutely isoregular graphs, while the other class, denoted $M(r)$ by Gol’fand, was presenting an infinite series of possible parameters. The graph $M(1)$ in this series corresponds to the famous Schläfli graph on 27 vertices, while $M(2)$ is the unique McLaughlin graph with the parameters $(275, 112, 30, 56)$. The existence of the graphs $M(r)$ for $r\ge 3$ remained open. (A brief introduction about this series is also available in [28].)

Klin and his colleagues made a lot of efforts to convince Gol’fand to publish his brilliant result (without the final page), however they never succeeded.

Gol’fand spent many years in attempts to reach the full desired result. After the collapse of the USSR he lived in relative poverty. At the end of the century he was killed in his apartment under unclear circumstances.

Around 1995, when he was still alive, Klin and Woldar established an attempt to publish a series of papers, starting from Gol’fand’s text as Part I and with [27] as Part II. Unfortunately after Gol’fand’s death the fate of his heritage still remains indefinite, this is one of the reasons why the work over the unfinished text [27] was conserved.

It should be mentioned that the original term $k$-regular suggested by Gol’fand lead to possible confusion. Indeed, for many researchers in graph theory, $k$-regular means regular of valency $k$. This is why Klin and Woldar in [27] decided to use the new term $k$ -isoregular, which does not imply any confusion.

We refer to [37] for all necessary precise formulations related to the concept of $k$-isoregularity.

One more approach, influenced by the consideration of graphs with the $t$-vertex condition is developed in publications by Wojdylo, see [41] for example.

9.3 Smith graphs

In 1975 a few papers were published by Smith, see for example [39], devoted to rank 3 permutation groups with the property that each of the two transitive subconstituents is also a rank 3 group. All possible feasible parameters for the corresponding SRG’s were presented in evident form. At that time the result was regarded as a program for further attacks toward a better understanding of such graphs. A few years later, with the announcement of the classification of finite simple groups, this research program became obsolete.

Since that time any SRG with the parameters described by Smith is called a Smith graph, be it rank 3 or not. A great significance of Smith graphs in the current context follows from the the paper [11], in which those SRG’s were investigated for which for each vertex $x$ both induced subgraphs $\varGamma _1(x)$ and $\varGamma _2(x)$ are also SRG’s. It is easy to check that this class of graphs strictly coincides with 3-isoregular graphs. (Note that the complete graph and the empty graph may be regarded as degenerate SRG’s.)

The main result in [11] claims that each 3-isoregular graph is either the pentagon, a pseudo Latin square or negative Latin square graph, or (up to complement) a Smith graph. Another significant ingredient of [11] is the established link of the class of 3-isoregular graphs with extremal properties of the Krein parameters of SRG’s and spherical $t$-designs (this link will be briefly mentioned in Sect. 9.6).

We should also mention Sect. 8 of [11] which deals with generalized quadrangles of order $(q,q^2)$. It was proved there that such geometrical structures coexist with orthogonal arrays of strength $3$ and order $q$, as well as with certain codes over an alphabet with $q$ letters. This coexistence creates an additional challenge for the reader to try to obtain our main result in absolutely different context, relying only on the geometrical analysis of the related codes.

We wish also to mention that 3-isoregular graphs are frequently called triply regular graphs, which from time to time are the subject of ongoing research, see [18]. Hopefully this section of our paper will help the modern investigators to better comprehend all the facets of these striking combinatorial objects.

The concept of a 3-isoregular graph can be generalized to an arbitrary symmetric association scheme. In this more general approach links with spherical designs are well visible, see [40].

9.4 The $4$-vertex condition

Here we provide more details regarding the consideration of the $4$-vertex condition.

The paper [22] (the last research input by Andrei Ivanov before his transfer to the software industry) introduces two infinite families of graphs on $2^{2n}$ vertices via the use of suitable finite geometries. It also contains a rigorous proof of a folklore claim that in the definition of the $t$-vertex condition for a regular graph it is enough to check its fulfillment just on edges and non-edges (that is, the inspection of loops is redundant).

Note that [22] contains interesting conjectures about the induced subgraphs of his graphs which still remain unnoticed by modern researchers (although one of the conjectures was confirmed in [37]).

Besides the well-known paper [19], Higman himself was considering graphs with the $4$-vertex condition in (at least) one more paper [20]. In particular, he considered the block graphs of Steiner triple systems with $m$ vertices (briefly $STS(m)$), which are known to be SRG’s. Highman proved that the block graph satisfies the $4$-vertex condition if the $STS(m)$ consists of the points and lines in projective space $PG(n,2)$ over the field of two elements, here, $m=2^n-1$. Besides this, the $4$-vertex condition may be satisfied for $STS(m)$, for $m\in \{9,13,25\}$.

While the cases $m=9$ and $m=13$ can be easily settled, the case $m=25$ remained open for four decades. Following the advice of Klin, Kaski et al. obtained the negative answer (see [26]), essentially relying on the use of computer and some extra clever ad hoc tricks (the complete enumeration of all $STS(25)$ looks hopeless at the moment).

There are also known a few sporadic proper (non-rank 3) SRG’s which satisfy the 4-vertex condition. The smallest such graphs have 36 vertices; they were carefully investigated in [29].

9.5 Generalizations for association schemes

Every SRG $\varGamma$ together with the complement $\overline{\varGamma }$ forms a symmetric association scheme with two classes (or of rank 3). Therefore it is natural to consider the concept of the $t$-vertex condition for arbitrary association schemes.

Non-symmetric schemes with two classes are equivalent to pairs of complementary doubly regular tournaments. Each such (skew-symmetric) scheme satisfies the $4$-vertex condition [32].

The situation for higher ranks is much more sophisticated and goes beyond the scope of this discussion. The first results in this direction were presented in [16] and [7], though without the evident use of association schemes. Further steps stem from [14].

9.6 Interactions with other problems

During the last two decades highly symmetrical association schemes, and in particular SRG’s, were used quite essentially in a number of significant research approaches in diverse parts of mathematics. For each such case it is not so easy to recognize immediately which properties of the related graphs or schemes are exactly requested. The source of such difficulties is as a rule a serious discrepancy in the languages adopted in the corresponding parts of mathematics.

A few examples are briefly mentioned below, each together with at least one striking reference.

Two decades ago Jaeger demonstrated in [24] how one could produce spin models for the applications in the theory of link invariants (in the sense of Jones), using suitable self-dual association schemes. The requested SRG’s should be 3-isoregular.

The problem of describing finite point systems in Euclidean space that satisfy some energy minimization criteria was attacked by Cohn et al. in a number of publications throughout the last decade. Surprisingly, they established links of putative optimal systems with some famous SRG’s, among them there are a few 3-isoregular graphs, see [13].

Deterministic polynomial factoring is considered in the framework of $m$-schemes as they are called in [23]. In fact, this class of objects is strictly related to diverse kinds of highly symmetrical association schemes (as they were mentioned in Sect. 9.5). The recent thesis [1] is a good source to digest sophisticated interactions, which appear in this new line of research.

Spherical designs are intimately related to the existence of some classes of SRG’s, in particular to putative $3$- and $4$-isoregular graphs. The survey [13] may be helpful as an initial introduction. In this context, the negative results by Bannai et al. presented in [2] imply the non-existence of infinitely many 4-isoregular graphs from the series $M(r)$ (still for infinitely many values of $r$ the question of existence remains open). This is, in a sense, a partial fulfillment of the foremost dream of the late Gol’fand. It should be mentioned that such an implication is not immediately visible for the uninitiated reader.

9.7 A paper by Christian Pech

The project presented in this paper has quite a long history, stemming from the author’s Master’s thesis, reflected and extended in [37]. The next steps were done by the author in his Ph.D. thesis [38], fulfilled under the supervision of Mikhail Klin and Felix Lazebnik. In [29] the first part of the results influenced by [38] was published together with further results and a detailed survey of all combinatorial structures related to exceptional graphs with the 4-vertex condition on 36 vertices.

It was Klin who convinced the author to come back to this area after many years and to make the obtained results available to the mathematical audience.

It should be mentioned that Christian Pech, another former student of Klin’s, for a long while was also interested in the investigations in the same area of graphs with the $t$-vertex condition. Pech’s acquaintance with a preliminary draft of this paper influenced him to go ahead with the preparation of his own contribution [36] in a reasonably self-contained form.

Below we present a short abstract of [36].

The text starts by develo** a more systematical approach to highly regular graphs, which cover naturally both graphs with the $t$-vertex condition and $k$-isoregular graphs. This allows serious stratification of many similar concepts and makes it possible to reach uniform proofs of many known and new results, as well as a network of auxiliary propositions. Pech uses very essentially the language and techniques of Category Theory; therefore reading his text requires special preparation from the reader not familiar with that theory. One of the significant final results is a construction of a new infinite family of non-rank 3 strongly regular graphs satisfying the 6-vertex condition. These graphs appear as induced subgraphs of point graphs of suitable generalized quadrangles, similar in spirit to the approach developed in [11].

The text [36] is expected to be available soon on ar**v.org. We hope that this together with the present article will stimulate a new wave of interest in the area of highly symmetrical strongly regular graphs.

10 Conclusion

We have shown that the point graphs of generalized quadrangles of order $(s,s^2)$ satisfy the 7-vertex condition. This provides us with an infinite family of strongly regular graphs satisfying that condition which have intransitive automorphism groups.

Hence, if Klin’s Conjecture holds (i.e., if there is a number $t_0$ such that the $t_0$-vertex condition implies a rank 3 automorphism group) then $t_0\ge 8$.

Still, the proof of this conjecture in its full generality appears intractable. If we restrict ourselves to point graphs of generalized quadrangles, then it looks reasonable to prove a similar statement, in particular since many characterization of the “classical” generalized quadrangles (which include those with a rank 3 group) are known.