The Smallest Strictly Neumaier Graph and its Generalisations
The Smallest Strictly Neumaier Graph and its Generalisations
复制标题
DOI：
10.37236/8189
复制
发表时间：
2018-09
期刊：
影响因子：
--
通讯作者：
R. J. Evans;S. Goryainov;Dmitry Panasenko
中科院分区：
文献类型：
--
作者：
R. J. Evans;S. Goryainov;Dmitry Panasenko
正则图中的正则团是这样的团，即该团外的每个顶点都与该团内的相同正数量的顶点相邻。我们继续研究边正则图中的正则团，这是由A.Neumaier在20世纪80年代提出的，目前引起了人们的兴趣。因此，我们定义Neumaier图为包含正则团的非完全边正则图，定义严格Neumaier图为非强正则Neumaier图。我们首先证明了关于Neumaier图及其可行参数元组的一些一般性结果。然后我们应用这些结果来确定最小的严格Neumaier图，它有$16$个顶点。接下来，我们求出所有不超过$24$点的严格Neumaier图的参数元组。最后，我们给出了两个图序列，每个图的元素都是一个严格的Neumaier图，它包含一个$2^{i}$-正则团(其中$i$是一个正整数)，并且具有边正则图的仿射极图的参数。这回答了G.格里夫斯和J·库伦最近提出的问题。
A regular clique in a regular graph is a clique such that every vertex outside of the clique is adjacent to the same positive number of vertices inside the clique. We continue the study of regular cliques in edge-regular graphs initiated by A. Neumaier in the 1980s and attracting current interest. We thus define a Neumaier graph to be an non-complete edge-regular graph containing a regular clique, and a strictly Neumaier graph to be a non-strongly regular Neumaier graph. We first prove some general results on Neumaier graphs and their feasible parameter tuples. We then apply these results to determine the smallest strictly Neumaier graph, which has $16$ vertices. Next we find the parameter tuples for all strictly Neumaier graphs having at most $24$ vertices. Finally, we give two sequences of graphs, each with $i^{th}$ element a strictly Neumaier graph containing a $2^{i}$-regular clique (where $i$ is a positive integer) and having parameters of an affine polar graph as an edge-regular graph. This answers questions recently posed by G. Greaves and J. Koolen.