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

Abstract

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 exist
non-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\).