Proof of a Conjecture on the Seidel Energy of Graphs

Saieed Akbari; Mostafa Einollahzadeh; Mohammad Mahdi Karkhaneei; Mohammad Ali Nematollahi

paper

Proof of a Conjecture on the Seidel Energy of Graphs

arXiv:1901.06692

Abstract

Let $G$ be a graph with the vertex set ${v_{1}, \dots, v_{n}}$ . The Seidel matrix of $G$ is an $n \times n$ matrix whose diagonal entries are zero, $ij$ -th entry is $- 1$ if $v_{i}$ and $v_{j}$ are adjacent and otherwise is $1$ . The Seidel energy of $G$ is defined to be the sum of absolute values of all eigenvalues of the Seidel matrix of $G$ . Haemers conjectured that the Seidel energy of any graph of order $n$ is at least $2 n - 2$ and, up to Seidel equivalence, the equality holds for $K_{n}$ . We establish the validity of Haemers' Conjecture in general.