A criterion for the \(t\)-vertex condition of graphs (Q1570760)

Let \(\Gamma\) be a graph and \(S\subseteq V(\Gamma)\) a set of vertices. A vertex \(x\) in \(V(\Gamma)\) is called a neighbor of \(S\) if it is adjacent to all elements of \(S\). The valency of \(S\) is the number of its neighbors. Let \(1\leq k\leq |V(\Gamma)|\). For any \(j\)-element subset \(S\) of \(V(\Gamma)\), \(j\leq k\), let the valency of \(S\) depend only on the isomorphism class of the subgraph of \(\Gamma\) induced by \(S\). Then \(\Gamma\) is called \(k\)-isoregular. Let \(t\) be a natural number. Let \(\Omega_t\) be the class of triples \((\Gamma,\eta,\theta)\), where \(\Gamma\) is a graph of order \(t\), and \(\eta\) and \(\theta\) are (not necessarily distinct) vertices of \(\Gamma\). Two elements \((\Gamma_1,\eta_1,\theta_1)\) and \((\Gamma_2,\eta_2,\theta_2)\) are said to be of the same type if there is an isomorphism \(\varphi: \Gamma_1\to \Gamma_2\) which maps \(\eta_1\) to \(\eta_2\) and \(\theta_1\) to \(\theta_2\). This establishes an equivalence relation on \(\Omega_t\); the equivalence classes are called types of the graphs. The set of types of order \(t\) is denoted by \({\mathcal T}_t\), and \({\mathcal T}=\bigcap _{t=0}^\infty {\mathcal T}_t\). For any type \(T\in {\mathcal T}\) we may choose a fixed representative \({\mathcal R}(T)=(\Gamma,\eta,\theta)\), which contains, besides \(\eta\) and \(\theta\), \(t-2\) additional vertices. The minimum of valencies of additional vertices in \(\Gamma\) is called the minimum valency of \(T\). Let \(S\) be an induced subgraph of \(\Gamma\) containing \(x\) and \(y\). \(S\) is said to be of type \(T\) with respect to \((x,y)\) if \((S,x,y)\in T\). Suppose for \(\Gamma\) that the number of induced subgraphs of type \(T\) with respect to \((x,y)\in E(\Gamma)\) does not depend on the choice of the edge \((x,y)\) for all types of graphs of \({\mathcal T}_1,\dots,{\mathcal T}_t\). Then \(\Gamma\) is said to satisfy the \(t\)-vertex condition on edges. In the same way we define the \(t\)-vertex condition on loops resp. nonedges. A graph is said to satisfy the \(t\)-vertex condition if it satisfies it on edges, nonedges, and loops. Theorem 3. Let \(\Gamma\) be a \(k\)-isoregular graph which satisfies the \((t-1)\)-vertex condition. For all types of graphs \(T\in {\mathcal T}_t\) with a minimal valency greater than \(k\) let the number of subgraphs of type \(T\) with respect to \((x,y)\) only depend on the color (edge, nonedge) of the pair \((x,y)\). Then \(\Gamma\) satisfies the \(t\)-vertex condition. Corollary 5. A \(k\)-isoregular graph \(\Gamma\), \(k>1\) satisfies the \((k+1)\)-vertex condition. It is proved that the two series of strongly regular graphs constructed by \textit{A. E. Brouwer, A. V. Ivanov} and \textit{M. H. Klin} [Combinatorica 9, No. 4, 339-344 (1989; Zbl 0709.05040)] and by \textit{A. V. Ivanov} [Combinatorica 9, No. 3, 255-260 (1989; Zbl 0706.05056)] satisfy the 5-vertex condition.