Laplacian Bounds for the Dissociation Number of Regular Graphs of Matrix Rings

Abstract

Let $Γ_n(q)$ be the graph whose vertices are the invertible matrices in $\Mat_n(\F_q)$, with two distinct matrices adjacent whenever their sum is singular. A dissociation set is a vertex set inducing a graph of maximum degree at most one. We study the dissociation number of $Γ_n(q)$ by embedding it as an induced subgraph of the total graph $T_n(q)$ on all of $\Mat_n(\F_q)$. A general Laplacian inequality for $k$-independent sets, together with an explicit character computation for the additive group of the matrix ring, gives parity-sensitive upper bounds. For fixed $n$, the resulting bound is of order at most $q^{n^2-n+1}$ for odd $q$ and at most $q^{n^2-2n+2}$ for even $q$. In particular, \[ \diss(Γ_n(q))\le q^{n^2-n+1}-1. \] In the other direction, the regular representation of the extension field $\F_{q^n}$ gives $\diss(Γ_n(q))\ge q^n-1$. We give complete proofs, including a self-contained derivation of the required matrix character sum, and determine the smallest case: $\diss(Γ_2(2))=3$.

Disclosure

“at produces the largest Laplacian eigenvalue: rank two in even characteristic and rank one in odd characteristic. Finally, the small- parameter analysis gives the exact value diss(Γ2 (2)) = 3. Declaration on the use of AI The author used generative AI tools to assist in discussing proof strategies, checking proofs, and improving the exposition. The author takes full responsibility for the mathematical arguments, results, and conclusions, all of which were carefully reviewed and verified”

PDF page 17

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T19:16:22.983180Z

Structural counts