Clique numbers of the total graphs of $2\times n$ and $3\times 3$ matrices

A. M. Maksaev ; V. V. Promyslov ; D. S. Sheshenya

Zapiski Nauchnykh Seminarov POMI, Computational methods and algorithms. Part XXXVII, Tome 534 (2024), pp. 128-146

Résumé

The total graph of the space of $m\times n$ matrices over a field $\mathbb F$ is the graph with vertex set $M_{m\times n}(\mathbb F)$ in which distinct matrices $A$ and $B$ are connected by an edge if and obly if rank$(A+B) \min(m,n)$. It is proved that over a field of order $q$, where $q$ is a power of an odd prime, the clique number of the total graph of $2\times n$ matrices equals $q^n$, whereas that of $3\times 3$ matrices is $O(q^6)$. Up to now, this issue has only been examined for $2\times 2$ matrices.