On quasi-strongly regular graphs

NEW

Problem: Goldberg’s conjecture is interpreted as follows: for fixed valency $k\ge 3$ and grade $p$, there are only finitely many finite simple quasi-strongly regular graphs. A graph is quasi-strongly regular with parameters $(n,k,a;c_1,\dots,c_p)$ if it is $k$-regular, every adjacent pair has exactly $a$ common neighbours, and every nonadjacent pair has one of exactly $p$ possible common-neighbour counts $c_i$.

Result: The conjecture is false.

For each odd $n\ge 7$, let $X_n=G(n,2)$ be the generalized Petersen graph with vertices

and edges

Then $X_n$ is connected cubic. For odd $n\ge 7$, the $u$-vertices form an $n$-cycle, the $v$-vertices also form an $n$-cycle, and the only cross-edges are the matching edges $u_i v_i$. Hence $X_n$ has no triangles or 4-cycles; indeed it has girth $5$, since

is a 5-cycle.

Now let

be the line graph of $X_n$. Since $X_n$ is cubic, $H_n$ is $4$-regular.

Adjacent vertices of $H_n$ correspond to adjacent edges $e=xy$, $f=xz$ of $X_n$. Their common neighbours in $H_n$ correspond to edges of $X_n$ adjacent to both $e$ and $f$. Because $X_n$ is cubic and triangle-free, the unique such edge is the third edge incident with $x$. Thus every adjacent pair in $H_n$ has exactly

common neighbour.

Nonadjacent vertices of $H_n$ correspond to disjoint edges of $X_n$. A common neighbour in $H_n$ is an edge of $X_n$ joining an endpoint of one edge to an endpoint of the other. Since $X_n$ has no triangles or 4-cycles, there can be at most one such edge. Hence every nonadjacent pair in $H_n$ has either $0$ or $1$ common neighbours.

Both values occur: the two disjoint edges $u_0u_1$ and $u_2u_3$ have the common neighbour $u_1u_2$ in $H_n$, while $u_0u_1$ and $u_4u_5$ have none. Therefore

so it has valency $k=4$ and grade $p=2$.

As $n$ ranges over odd integers $n\ge 7$, the graphs $H_n$ have $3n$ vertices, hence are pairwise nonisomorphic. Thus there are infinitely many quasi-strongly regular graphs of fixed valency $4$ and fixed grade $2$. This disproves the conjecture.

Citation: Goldberg, “On quasi-strongly regular graphs,” Linear and Multilinear Algebra, for the conjecture and definition. The generalized Petersen graphs are standard; see M. E. Watkins, “A theorem on Tait colorings with an application to the generalized Petersen graphs,” J. Combinatorial Theory 6 (1969), 152–164.