no. 14 · Friday 13 November 2026
Strictly Deza Graphs among the Prime Graphs of Solvable Groups
Abstract
We study strictly Deza graphs that occur as prime graphs of finite solvable groups and admit a partition into two cliques. Using Gruber's characterization of the prime graphs of finite solvable groups, we relate this problem to bipartite $(0,2)$-graphs. We first show that a non-complete regular graph with a partition into two cliques has equal parts. For a graph of diameter two, writing $F$ for its $c$-regular complement on $2m$ vertices, the Deza condition is equivalent to every component of $F$ being a bipartite $(0,2)$-graph. Within this class, strongly regular graphs occur exactly when $c=1$; we give elementary descriptions for $c=2$ and $c=3$, and translate the existing classification of bipartite $(0,2)$-graphs of valency at most eight. A counting argument yields $m\ge1+c(c-1)/2$, with equality corresponding to biplanes. These observations recover the ten feasible parameter pairs for $m\le7$ without enumeration and give infinite families of strictly Deza prime graphs. We also exhibit a known eight-vertex strictly Deza graph whose complement is triangle-free and three-colourable but not bipartite, showing that clique cover number three occurs.
- fields
- Combinatorics