Quasi-strongly regular graphs of grade three with diameter two

Abstract

A quasi-strongly regular graph of grade $p$ with parameters $(n,k,a;c_1,\dots ,c_p)$ is a $k$-regular graph of order $n$ such that any two adjacent vertices share $a$ common neighbours and any two non-adjacent vertices share $c_i$ common neighbours for some $1\le i\le p$. This is a generalization of a strongly regular graph. In this paper, we focus on strictly quasi-strongly regular graphs of grade $3$ with $c_i=k-i$ for $i=1,2,3$. The main result is to show the sharp bounds of order $n$ for a given $k\ge 4$. Furthermore, by this result, we characterize all of these graphs whose $n$ satisfies upper or lower bounds.

References in corpus (1)

• On strictly Deza graphs with parameters (n,k,k-1,a)