RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. POMI, 2024 Volume 534, Pages 128–146 (Mi znsl7480)

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

A. M. Maksaevab, V. V. Promyslovab, D. S. Sheshenyaa

a National Research University Higher School of Economics, Moscow
b Moscow Center for Fundamental and Applied Mathematics

Abstract: 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.

Key words and phrases: clique number of a graph, total graph, combinatorial matrix theory.

UDC: 519.174

Received: 01.10.2024



© Steklov Math. Inst. of RAS, 2025