Construction of two infinite classes of strongly regular graphs using magic squares

Lepović, Mirko

Serdica Mathematical Journal, Tome 46 (2021) no. 3, pp. 235-252

Résumé

We say that a regular graph \(G\) of order $n$ and degree \(r\ge 1\) (which is not the complete graph) is strongly regular if there existnon-negative integers \(\tau\) and \(\theta\) such that \(|S_i\cap S_j| =\tau\) for any two adjacent vertices \(i\) and \(j\) and \(|S_i\cap S_j|= \theta\) for any two distinct non-adjacent vertices \(i\) and \(j\), where \(S_k\) denotes the neighborhood of the vertex \(k\). Using a method for constructing the magic and semi-magic squares of order \(2k+1\), we have created two infinite classes of strongly regular graphs (i) strongly regular graph of order \(n = (2k+1)^2\) and degree \(r = 8k\) with \(\tau = 2k+5\) and \(\theta = 12\) and (ii) strongly regular graph of order \(n = (2k+1)^2\) and degree \(r = 6k\) with \(\tau = 2k+1\) and \(\theta = 6\) for \(k\ge 2\).

Détail

Keywords: strongly regular graph, magic square, conference graph, 05C50