Motivated from the concept of strong regularity in the graph theory, few varieties of definitions for strongly regular signed graphs have been introduced. The initial one, which is due to Zaslavsky and the others are given by Stanic and Ramezani. The definition given by Stanic covers all the others. In this paper we provide some constructions for each of the definitions.
A signed graph is a graph \(\Gamma=(V_{\Gamma},E_{\Gamma})\) together with a sign function, so called a signature, on its edge set, say \(\sigma:E\longrightarrow\{+1,-1\}\). A signed graph is normally denoted by \(\Sigma=(\Gamma,\sigma)\). The graph \(\Gamma\) is called the ground of \(\Sigma=(\Gamma,\sigma)\) and we denote it by \(|\Sigma|\). By a vertex or edge of a signed graph we mean those of its ground. The vertex degree of a vertex \(v\) of \(\Sigma\), denoted by \(d_{\Sigma}(v)\), is the vertex degree of \(v\) in \(\Gamma\), that is, \(d_{\Gamma}(v)\). The positive and negative degrees of \(v\), denoted by \(d_{\Sigma}^{+}(v)\), \(d_{\Sigma}^{-}(v)\), is respectively defined to be the number of positive and negative edges incident with \(v\) in \(\Sigma\), if there is no doubt about \(\Sigma\), then we simply write \(d_{v}^{+}\) and \(d_{v}^{-}\). The net degree of a vertex \(v\) is \(d_{v}^{+}-d_{v}^{-}\). For a signed graph \(\Sigma=(\Gamma,\sigma)\), by \(\Sigma^{+}\) and \(\Sigma^{-}\), we mean the following unsigned graphs: \[\Sigma^{+}=(V_{\Gamma},E_{\Sigma^{+}}) \qquad\text{and}\qquad \Sigma^{-}=(V_{\Gamma},E_{\Sigma^{-}}),\] where \[E_{\Sigma^{+}}=\sigma^{-1}(+1) \qquad\text{and}\qquad E_{\Sigma^{-}}=\sigma^{-1}(-1).\]
The graph \(\Sigma^{+}\) is called the positive subgraph of \(\Sigma\) and \(\Sigma^{-}\) is called its negative subgraph. A signed graph is called regular if both the positive and negative subgraphs are regular. It is also said to have balanced degree if the net degrees of its vertices is constant.
By switching at a vertex \(v\) of \(\Sigma\), we mean to change the sign of all the edges incident with \(v\). Two signed graphs \((\Gamma,\sigma_{1})\) and \((\Gamma,\sigma_{2})\) are said to be switching equivalent if one is obtained from the other by a sequence of switchings, otherwise they are called switching non-equivalent. A cycle in a signed graph \(\Sigma\) is called balanced (unbalanced) if it contains an even (odd) number of negative edges. In [11] Zaslavsky provides a nice characterization of switching equivalent signed graphs, which states that \((\Gamma,\sigma_{1})\) and \((\Gamma,\sigma_{2})\) are switching equivalent if and only if they share same set of unbalanced cycles.
Definition 1.1. An \(n\)-class association scheme consists of a set \(X\) together with a partition \(\mathcal{P}\) of \(X\times X\) into \(n+1\) binary relations, \(R_{0},R_{1},\ldots,R_{n}\), which satisfy the following:
(i) \(R_{0}=\{(x,x)\mid x\in X\}\),
(ii) \(R_{i}^{*}:=\{(y,x)\mid(x,y)\in R_{i}\}\in\mathcal{P}\), and
(iii) if \((x,y)\in R_{k}\), then the number of \(z\in X\) such that \((x,z)\in R_{i}\) and \((z,y)\in R_{j}\) is a constant \(p_{ij}^{k}\) depending on \(i,j,k\).
An association scheme is symmetric whenever each of the corresponding binary relations are symmetric. It is well-known that the relations of a symmetric 2-class association scheme are equivalent to strongly regular graphs. To each binary relation \(R_{i}\) of an \(n\)-class association scheme, one can associate a \((0,1)\)-matrix \(\mathbf{A}_{i}\) of order \(n\) as follows. The rows and columns of \(\mathbf{A}_{i}\) are indexed with elements of \(X\) and the \((x,y)\) entry \(\mathbf{A}_{i}(x,y)\) is \[\mathbf{A}_{i}(x,y)= \begin{cases} 1, & \text{if }(x,y)\in R_{i},\\ 0, & \text{otherwise.} \end{cases}\]
Let \(\mathcal{A}=\langle\mathbf{A}_{0},\mathbf{A}_{1},\ldots,\mathbf{A}_{n}\rangle\). Then, the following conditions hold (see [5]):
(1) \(\mathbf{A}_{0}=\mathbf{I}\).
(2) \(\mathbf{A}_{0}+\mathbf{A}_{1}+\cdots+\mathbf{A}_{n}=\mathbf{J}\), where \(\mathbf{J}\) is the all 1’s matrix.
(3) For each \(i\), \(\mathbf{A}_{i}^{T}\in\mathcal{A}\), where \(T\) signifies the transpose.
(4) \(\mathbf{A}_{i}\mathbf{A}_{j}=\mathbf{A}_{j}\mathbf{A}_{i}\in\mathcal{A}\), that is \(\mathcal{A}\) is a symmetric algebra with respect to matrix multiplication.
Given two signed graphs \(\Sigma_{1}=(\Gamma_{1},\sigma_{1})\) and \(\Sigma_{2}=(\Gamma_{2},\sigma_{2})\), their cartesian product \(\Sigma_{1}\times\Sigma_{2}\) is the signed graph \((\Gamma_{1}\times\Gamma_{2},\sigma)\), where the corresponding sign function \(\sigma\) is as follows: if \(u\in V_{\Gamma_{1}}\) and \(vw\in E_{\Gamma_{2}}\), then \(\sigma((u,v)(u,w))=\sigma_{2}(vw)\), and similarly if \(uv\in E_{\Gamma_{1}}\) and \(w\in V_{\Gamma_{2}}\), then \(\sigma((u,w)(v,w))=\sigma_{1}(uv)\). This is a special kind of non-complete extended \(p\)-sum of signed graphs, known as NEPS of signed graphs. For more details see [4].
In [12] Zaslavsky has defined the concept of very strong regularity, which is the following.
Definition 1.2. [12] A signed graph is a very strongly regular signed graph, VSRSG for short, if its adjacency matrix satisfies, \[\mathbf{A}^{2}-t\mathbf{A}-k\mathbf{I} =\rho\overline{\mathbf{A}} \quad\text{and}\quad \mathbf{A}\mathbf{j}=\rho_{0}\mathbf{j},\] for some constants \(t,k,\rho,\rho_{0}\). Here \(\overline{\mathbf{A}}\) is the adjacency matrix of the complement of \(|\Sigma|\). The combinatorial interpretation of the above parameters follows:
a. \(|\Sigma|\) is \(k\)-regular, with \(n\) vertices,
b. \(\rho_{0}=d_{v}^{+}-d_{v}^{-}\), for every vertex \(v\), hence \(\Sigma\) is regular.
c. \(t=t_{xy}^{+}-t_{xy}^{-}\) where \(t_{xy}^{+}\) and \(t_{xy}^{-}\) are the numbers of positive and negative triangles on an edge \(e=xy\),
d. \(\rho=\rho_{xy}^{+}-\rho_{xy}^{-}\) for any pair \(x,y\) of nonadjacent vertices, where \(\rho_{xy}^{+}\), \(\rho_{xy}^{-}\) are the numbers of positive and negative length two paths joining the vertices,
e. \(t\) and \(\rho\) are independent of the choices of adjacent or nonadjacent vertices.
We denote a VSRSG with the above parameters with \(\operatorname{VSRSG}(n,k,\rho_{0},t,\rho)\).
A definition of the same essence is due to Ramezani, stated in [6].
Definition 1.3. [6] A signed regular graph \(\Sigma\) is called F-strongly regular signed graph, FSRSG for short, whenever it satisfies the following conditions:
(i) \(|\Sigma|\) is \(k\)-regular, with \(n\) vertices,
(ii) if \(\Sigma\) contains at least one positive edge, then there exist \(t\in\mathbb{Z}\) such that \(t_{xy}^{+}-t_{xy}^{-}=t\), for any edges \(xy\),
(iii) there exist \(\rho\in\mathbb{Z}\) such that \(\rho_{xy}^{+}-\rho_{xy}^{-}=\rho\), for all non-adjacent vertices \(x\) and \(y\), where \(\rho\) is chosen as in Definition 1.2. We denote a FSRSG with the above parameters with \(\operatorname{FSRSG}(n,k,t,\rho)\).
Note that a VSRSG can be regarded as a regular FSRSG. As a generalization for both of the above definitions Stanic has provided the notion of strongly regular signed graphs in [8]. We refer to that by SSRSG, for convenience. The following is his definition, written in our notations.
Definition 1.4. [8] A signed regular graph \(\Sigma\) is said to be a SSRSG whenever it satisfies the following conditions:
(i) \(|\Sigma|\) is \(k\)-regular, with \(n\) vertices.
(ii) \(\Sigma\) is neither homogenous complete nor totally disconnected,
(iii) if \(\Sigma\) contains at least one positive edge, then there exist \(a\in\mathbb{Z}\) such that \(t_{xy}^{+}-t_{xy}^{-}=a\), for all positive edges \(xy\),
(iv) if \(\Sigma\) contains at least one negative edge, then there exist \(b\in\mathbb{Z}\) such that \(t_{xy}^{+}-t_{xy}^{-}=b\), for all negative edges \(xy\),
(v) there exist \(\rho\in\mathbb{Z}\) such that \(\rho_{xy}^{+}-\rho_{xy}^{-}=\rho\), for all non-adjacent vertices \(x\) and \(y\). We denote a SSRSG with the above parameters with \(\operatorname{SSRSG}(n,k,a,b,\rho)\).
If in Definition 1.4, the signed graph is regular and the parameters \(a\) and \(b\) happens to be equal then the signed graph will provide conditions of Definition 1.2. In Definitions 1.3 and 1.4 the signed graphs do not require to be regular. That is, the condition b in Definition 1.2 is not required for the rest. Moreover, in Definition 1.4 the parameter \(t\) is not the same for positive and negative edges whereas in Definitions 1.2 and 1.3 it is essential to be consistent. A distinguished point about FSRSG and SSRSG’s is that if a graph is a FSRSG (or SSRSG) then in some cases, switching equivalent of the signed graph has also the same property. This is a good property as switching is a crucial supplement for signed graphs, it doesn’t hold for Definition 1.2. We call a signed graph strongly regular if it is either VSRSG, FSRSG, or SSRSG. The SSRSG’s cover all the other notions, but we won’t use this for general meaning, distinguishing the properties precisely. Our purpose at this paper is to provide some examples and constructions for each of the mentioned strongly regular signed graphs.
In [8], the author has classified some families of SSRSG’s. Some examples for FSRSG and VSRSG can be found in [7], where Ramezani has classified and constructed some signed graphs with only two distinct eigenvalues. It turns out that all the strongly regular signed graphs with \(\rho=0\), and the extra constraint \(a=b\) in Definition 1.4, has only two distinct adjacency eigenvalues. Moreover, these are the only signed graphs with two distinct eigenvalues, see [8].
A two-graph \(\mathcal{G}\) is a set consisting of 3-subsets of a finite set \(X\), say set of vertices, such that every 4-subset of \(X\) contains an even number of 3-subsets of \(\mathcal{G}\). A two-graph is called regular if every pair of vertices in \(X\) lies in the same number of 3-subsets of the two-graph. Two-graphs are extensively studied in the literature. There is a deep relation between two-graphs and signed complete graphs, see as example [2, 9, 11].
Our first construction is based on the association schemes. More precisely we use 3-class association schemes to construct a SSRSG.
Definition 2.1. For a symmetric 3-class association scheme on a set \(X\), say \(\mathcal{R}=\{R_{0},R_{1}, R_{2},R_{3}\}\), the signed graph \(\Gamma_{i,j}\) is defined as follows. Let \(|\Gamma_{i,j}|=(X,E_{i,j})\) be its ground, where \[E_{i,j}=\{xy\mid(x,y)\in R_{i}\cup R_{j}\},\] and define its signature \(\sigma:E_{i,j}\longrightarrow\{+1,-1\}\) by \[\sigma(xy)= \begin{cases} +1 & \text{if }(x,y)\in R_{i},\\ -1 & \text{if }(x,y)\in R_{j}. \end{cases}\]
Note that since for \(i\ne j\) the relations \(R_{i}\) and \(R_{j}\) are disjoint, therefore the signed graphs \(\Gamma_{i,j}\) are well-defined. We may consider the signed graph \(\Gamma_{i,i}\) as a signed graph in which there exist two parallel edges, one negative and one positive, between vertices \(x,y\), whenever \((x,y)\in R_{i}\).
Theorem 2.2. For any 3-class association scheme on a set \(X\), say \(\mathcal{R}=\{R_{0},R_{1},R_{2},R_{3}\}\), the signed graph \(\Gamma_{i,j}\) is a regular SSRSG, for \(i,j=1,2,3\). Moreover, if for an example \(\Gamma_{i,j}\) the equality \(a=b\) holds on the corresponding parameters, then the signed graph \(\Gamma_{i,j}\) is a VSRSG.
Proof. We check the conditions i-v of Definition 1.4.
(i), (ii) Hold obviously.
(iii) Let \(xy\) be a positive edge of \(\Gamma_{i,j}\), i.e \((x,y)\in R_{i}\), the number of positive triangles containing \(xy\) is equal to the number of common positive or common negative neighbors of \(x\) and \(y\). By Definitions 1.1 and 2.1 the number of common positive (negative) neighbors of \(x\) and \(y\) are the number of \(z\in X\) such that \((x,z)\in R_{i}\) and \((z,y)\in R_{i}\) (\((x,z)\in R_{j}\) and \((z,y)\in R_{j}\)), which is \(p_{ii}^{i}\) (\(p_{jj}^{i}\)), hence \(t_{xy}^{+}=p_{ii}^{i}+p_{jj}^{i}\). On the other hand the number of negative triangles containing \(xy\) equals \(t_{xy}^{-}=p_{ij}^{i}+p_{ji}^{i}\), with a similar argument. Hence \(a=p_{ii}^{i}+p_{jj}^{i}-2p_{ij}^{i}\), this is consistent for all the positive edges by definition of an association scheme.
(iv) If \(xy\) is a negative edge, the number of positive (negative) triangles containing \(xy\) equals \(p_{ij}^{j}+p_{ji}^{j}\) (\(p_{ii}^{j}+p_{jj}^{j}\)), hence at this case \(b=2p_{ij}^{j}-p_{ii}^{j}-p_{jj}^{j}\), which is again consistent for all negative edges.
(v) Suppose that \(x,y\) are non-adjacent, so \((x,y)\in R_{k}\) (\(k=\{1,2,3\}\setminus\{i,j\}\)). At this case \(\rho_{xy}^{+}\) equals the number of \(z\in X\) where \((x,z)\in R_{i}\) and \((z,y)\in R_{i}\) or \((x,z)\in R_{j}\) and \((z,y)\in R_{j}\) that is \(p_{ii}^{k}+p_{jj}^{k}\) by the definition. Similarly, \(\rho_{xy}^{-}\) is equal to \(p_{ij}^{k}+p_{ji}^{k}\) thus \(c=p_{ii}^{k}+p_{jj}^{k}-2p_{ij}^{k}\), which is independent of choosing \(x,y\) by definition of association schemes. Hence the assertion follows. \(\square\)
Remark 2.3. For a vertex \(x\in X\) of \(\Gamma_{i,j}\) the number of positive (negative) edges incident with \(x\) is \(p_{ii}^{0}\) (\(p_{jj}^{0}\)). Therefore, the signed graphs \(\Gamma_{i,j}\) are regular with net-degree \(p_{ii}^{0}-p_{jj}^{0}\), which is invariant. Moreover, the result is \[\operatorname{SSRSG}\bigl(n,p_{ii}^{0}+p_{jj}^{0}, p_{ii}^{i}+p_{jj}^{i}-2p_{ij}^{i}, 2p_{ij}^{j}-p_{ii}^{j}-p_{jj}^{j}, p_{ii}^{k}+p_{jj}^{k}-2p_{ij}^{k}\bigr).\]
We provide examples of SSRSG’s and VSRSG’s via 3-class association schemes, which is introduced in [10].
Example 2.4. The 3-class Johnson scheme \(J(n,3)\) also known as the tetrahedral scheme, is defined on the 3-subsets of an \(n\)-set. Two subsets are in relation \(R_{i}\) if they intersect in \(3-i\) elements.
| \(\Gamma_{i,j}\) | \(\Gamma_{1,2}\) | \(\Gamma_{1,3}\) | \(\Gamma_{2,3}\) |
|---|---|---|---|
| \(k\) | \((3n^{2})/2-(15n)/2+9\) | \(n^{3}/6-2n^{2}+(65n)/6-19\) | \(n^{3}/6-n^{2}/2-(8n)/3+8\) |
| \(a\) | \(n^{2}-11n+30\) | \(n^{3}/6-(5n^{2})/2+(40n)/3-22\) | \(n^{3}/6-(9n^{2})/2+(115n)/3-100\) |
| \(b\) | \(-n^{2}/2+(11n)/2-15\) | \(-n^{3}/6+(7n^{2})/2-(55n)/3+20\) | \(-n^{3}/6+(13n^{2})/2-(217n)/3+236\) |
| \(c\) | \(9(n-8)\) | \(n^{3}/6-3n^{2}+(95n)/6-21\) | \(n^{3}/6-(5n^{2})/2+(40n)/3-24\) |
Remark 2.5. The parameters mentioned in Table 1 are obtained by a simple computer programming. Theorem 2.2 implies that
signed graphs \(\Gamma_{1,3}\) corresponding to Johnson Schemes \(J(7,3)\), and \(J(9,3)\) are VSRSG.
signed graphs \(\Gamma_{1,2}\) corresponding to Johnson Schemes \(J(5,3)\), and \(J(6,3)\) are VSRSG.
Moreover, their corresponding \(\rho\) parameter is equal to zero, which leads to a signed graph with only two distinct eigenvalues, see [7, 8].
Example 2.6. For positive integers \(m,n\), the rectangular scheme \(R(m,n)\), has as vertices the pairs \((i,j)\) with \(i=1,2,\ldots,m\) and \(j=1,2,\ldots,n\). For two distinct pairs, the following three classes may be considered.
\(R_{1}\): contains those pairs, which agree in the first coordinate,
\(R_{2}\): those, which agree in the second coordinate,
\(R_{3}\): those pairs, which do not agree in any coordinate.
Based on this scheme we have SSRSG’s with the following parameters.
| \(\Gamma_{i,j}\) | \(\Gamma_{1,2}\) | \(\Gamma_{1,3}\) | \(\Gamma_{2,3}\) |
|---|---|---|---|
| \(k\) | \(m+n-2\) | \(mn-n\) | \(mn-m\) |
| \(a\) | \(n-2\) | \(m(n-2)\) | \(n(m-2)\) |
| \(b\) | \(2-m\) | \(-(n-2)(m-4)\) | \(-(m-2)(n-4)\) |
| \(c\) | \(-2\) | \((n-1)(m-4)\) | \((m-1)(n-4)\) |
Remark 2.7. The signed graphs \(\Gamma_{1,3}\) (\(\Gamma_{2,3}\)) corresponding to the scheme \(R(2,n)\) (\(R(n,2)\)) provide VSRSG’s with the following parameters. \[\operatorname{VSRSG}(2n,2n-2,0,2(n-2),-2(n-1)).\]
Example 2.8. The 3-class Hamming scheme \(H(3,q)\) is defined on the triples on \(q\) symbols (words of length 3 over an alphabet with \(q\) letters), where two triples are in relation \(R_{i}\) if they differ in \(i\) coordinates, for \(i=0,1,2,3\).
| \(\Gamma_{i,j}\) | \(\Gamma_{1,2}\) | \(\Gamma_{1,3}\) | \(\Gamma_{2,3}\) |
|---|---|---|---|
| \(k\) | \(3q^{2}-3q\) | \(q^{3}-3q^{2}+6q-4\) | \(q^{3}-3q+2\) |
| \(a\) | \(2q^{2}-9q+6\) | \(q^{3}-4q^{2}+6q-4\) | \(q^{3}-8q^{2}+18q-10\) |
| \(b\) | \(-(q^{2}-6q+12)\) | \(-q^{3}+6q^{2}-6q-4\) | \(-q^{3}+12q^{2}-42q+44\) |
| \(c\) | \(6(q-3)\) | \(q^{3}-5q^{2}+6q\) | \(q^{3}-4q^{2}+3q\) |
Remark 2.9. The following signed graphs are VSRSG’s arisen from the scheme \(H(3,q)\), by Theorem 2.2.
The signed graphs \(\Gamma_{1,2}\), and \(\Gamma_{1,3}\), corresponding to \(H(3,2)\), and \(H(3,3)\),
The signed graph \(\Gamma_{2,3}\), corresponding to \(H(3,3)\).
We summarize the parameters of the obtained VSRSG’s in the following Table 4.
| Signed graph | the scheme | \(n\) | \(k\) | \(\rho_{0}\) | \(t\) | \(\rho\) |
|---|---|---|---|---|---|---|
| \(\Gamma_{1,2}\) | \(J(5,3)\) | \(10\) | \(9\) | \(3\) | \(0\) | \(0\) |
| \(\Gamma_{1,2}\) | \(J(6,3)\) | \(20\) | \(18\) | \(0\) | \(0\) | \(-18\) |
| \(\Gamma_{1,3}\) | \(J(7,3)\) | \(35\) | \(16\) | \(8\) | \(6\) | \(0\) |
| \(\Gamma_{1,3}\) | \(J(9,3)\) | \(84\) | \(38\) | \(-2\) | \(17\) | \(0\) |
| \(\Gamma_{1,3}\) (\(\Gamma_{2,3}\)) | \(R(2,n)\)(\(R(n,2)\)) | \(2n\) | \(2n-2\) | \(0\) | \(2(n-2)\) | \(-2(n-1)\) |
| \(\Gamma_{1,3}\) | \(H(3,2)\) | \(8\) | \(4\) | \(2\) | \(0\) | \(0\) |
| \(\Gamma_{1,2}\) | \(H(3,2)\) | \(8\) | \(6\) | \(0\) | \(-4\) | \(-6\) |
| \(\Gamma_{1,3}\) | \(H(3,3)\) | \(27\) | \(14\) | \(-2\) | \(5\) | \(0\) |
| \(\Gamma_{2,3}\) | \(H(3,3)\) | \(27\) | \(20\) | \(4\) | \(-1\) | \(0\) |
In this section we provide some examples of signed strongly regular graphs on a complete graph. The following proposition will be useful later.
Proposition 3.1. [11] If \(\Sigma\) is a signed complete graph, then
(1) The set of unbalanced triangles of \(\Sigma\) is a two-graph. And any two-graph is constructed by the same way for some signed complete graph.
(2) If \(\Sigma_{1}\), and \(\Sigma_{2}\) are signed complete graphs, then they share the same set of unbalanced triangles if and only if \(\Sigma_{1}\), and \(\Sigma_{2}\) are switching equivalent.
Let \(\mathcal{G}\) be a two-graph on the set \(X\). For any \(x\in X\), we define a graph \(\Gamma_{x}\) with vertex set \(X\) where vertices \(y\) and \(z\) are adjacent if and only if \(\{x,y,z\}\) is in \(\mathcal{G}\). The following result on two-graphs is mentioned in [2].
Proposition 3.2. [2] Let \(\mathcal{G}\) be a non-trivial two-graphs on the set \(X\), \(\mathcal{G}\) is regular if and only if for some \(x\in X\) the graph \(\Gamma_{x}\) is a strongly regular graph with \(k=2\mu\).
We have a similar classification for SSRSG’s.
Theorem 3.3. The signed graph \(\mathcal{K}=(K_{n},\sigma)\) is a regular SSRSG if and only if \(\mathcal{K}^{+}\) is a non-trivial strongly regular graph.
Proof. First suppose that \(\mathcal{K}=(K_{n},\sigma)\) and \(\mathcal{K}^{+}\) is a non-trivial strongly regular graph with parameters \(\operatorname{SRG}(n,k,\lambda,\mu)\). Note that \(\mathcal{K}^{-}\) is also a strongly regular graph with parameters \(\operatorname{SRG}(n,n-k-1,n-2-2k+\mu,n-2k+\lambda)\). We claim that the signed graph \(\mathcal{K}\) is a SSRSG. We check the conditions (iii)-(v) in Definition 1.4, as (i) and (ii) are obvious. Let \(xy\) be a positive edge in \(\mathcal{K}\). Note that a positive triangle containing \(xy\) contains a totally positive, or totally negative 2-path between \(x,y\), but respectively their number is \(\lambda,n-2k+\lambda\). Hence the number of positive triangles containing \(xy\) is equal to \(\lambda+n-2k+\lambda\). The negative triangles are the rest of triangles containing \(x,y\), thus we will have \[ a=\lambda+n-2k+\lambda-(n-2-\lambda-n+2k-\lambda) =4\lambda-4k+n+2.\tag{1}\]
Now suppose that \(xy\) is a negative edge. Thus any negative triangle is formed by adding a totally positive, or totally negative 2-path between \(x,y\), hence the number of negative triangles containing \(xy\) is equal to \(n-2-2k+\mu+\mu\), similar to the previous discussion, the number of positive triangles containing \(xy\) is equal to the following: \[ b=n-2-(n-2-2k+\mu+\mu)-(n-2-2k+\mu+\mu) =-n+4k-4\mu+2.\tag{2}\]
There is no non-adjacent pair of vertices in \(\mathcal{K}\), thus (v) holds as well. Therefore, \(\mathcal{K}\) is a SSRSG with parameters \(\operatorname{SSRSG}(n,n-1,4\lambda-4k+n+2,-n+4k-4\mu+2,0)\). Conversely, assume \(\mathcal{K}=(K_{n},\sigma)\) is a regular SSRSG with corresponding parameters \((n,n-1,a,b,0)\), with a \(k\)-regular positive subgraph, that is \(\mathcal{K}^{+}\) is of valency \(k\). For a positive edge \(xy\), let us define
\(A=\{z\in V(\mathcal{K})\setminus\{x,y\};\sigma(xz)=\sigma(yz)=1\}\),
\(B=\{z\in V(\mathcal{K})\setminus\{x,y\};\sigma(xz)=\sigma(yz)=-1\}\),
\(C=\{z\in V(\mathcal{K})\setminus\{x,y\};\sigma(xz)=-1,\sigma(yz)=1\}\),
\(D=\{z\in V(\mathcal{K})\setminus\{x,y\};\sigma(xz)=1,\sigma(yz)=-1\}\).
Then we have the following equalities, by Definition 1.4. \[\left\{ \begin{aligned} |A|+|B|+|C|+|D|&=n-2,\\ -|A|-|B|+|C|+|D|&=a,\\ |C|+|B|&=n-k-1,\\ |D|+|B|&=n-k-1, \end{aligned} \right.\]
The above system of linear equations has a unique solution as determinant of the matrix of coefficients is non-zero. This implies that for any positive edge \(xy\) the number of common positive neighbors of \(x,y\) is a constant, say \(\lambda\), more precisely \(\lambda=3(n-2)/4-a/4-n+k+1\). Now suppose that \(xy\) is a negative edge, that is actually a non-edge in \(\mathcal{K}^{+}\). If the sets \(A,B,C,D\) are chosen as before, the following equalities hold, by Definition 1.4. \[\left\{ \begin{aligned} |A|+|B|+|C|+|D|&=n-2,\\ |A|+|B|-|C|-|D|&=b,\\ |B|+|C|&=n-k-2,\\ |B|+|D|&=n-k-2, \end{aligned} \right.\]
Similarly, the above system of linear equations has a unique solution, therefore for any non-edge \(xy\) of \(\mathcal{K}^{+}\), the number of common positive neighbors of \(x,y\), that is \(|A|\) is a constant, say \(\mu\), more precisely \(\mu=3(n-2)/4+b/4-n+2+k\). Thus \(\mathcal{K}^{+}\), is a strongly regular graph. \(\square\)
Theorem 3.4. A signed graph \(\mathcal{K}=(K_{n},\sigma)\) is a VSRSG, if and only if the graph \(\mathcal{K}^{-}\) is a strongly regular graph, \(\operatorname{SRG}(n,k,\lambda,\mu)\), such that \(n+2\lambda+2\mu=4k\).
Proof. By Theorem 3.3, the graph \(\mathcal{K}^{-}\) is a strongly regular graph. Now by letting \(a=b\), in equalities (1) and (2), the assertion follows. \(\square\)
By Proposition 10.3.2 of [3], a strongly regular graph in which parameters satisfy the equality \(n+2\lambda+2\mu=4k\) are associated with two-graphs. By the view of the table of parameters of strongly regular graphs by Brouwer, see [1], the smallest strongly regular graph, which satisfies \(n+2\lambda+2\mu=4k\) is the complement of the Petersen graph. So the graph \((K_{10},\sigma_{P^{c}})\) is a VSRSG, more precisely \(\operatorname{VSRSG}(10,9,6,0,0)\). Note that \(\sigma_{P^{c}}\) is the sign function in which the edges of the complement of Petersen graph are assigned negative sign, while the other edges are positive.
In the following theorem we have classified all the signed complete graphs that are a FSRSG. It is a consequence of some old results on two-graphs.
Theorem 3.5. The signed graph \(\mathcal{K}=(K_{n},\sigma)\) is a FSRSG if and only if \(\mathcal{K}\) is switching equivalent to a signed graph \(\mathcal{K}’=(K_{n},\sigma’)\), so that the graph \(\mathcal{K}^{\prime-}\) is isomorphic to \(K_{1}\cup\Gamma\), where \(\Gamma\) is a strongly regular graph with \(k=2\mu\).
Proof. Let \(\mathcal{K}=(K_{n},\sigma)\) be a \(\operatorname{FSRSG}(n,n-1,t,0)\). It is well-known that the set of unbalanced triangles of \(\mathcal{K}\), say \(\mathcal{G}\) is a two-graph. By the notations used in Definition 1.3, every pair \(x,y\) of vertices of graph belong to \(t_{xy}^{-}\) unbalanced triangles. On the other hand we have the following equalities \[t=t_{xy}^{+}-t_{xy}^{-},\] \[\binom{n}{3}=t_{xy}^{+}+t_{xy}^{-}.\]
The above equalities imply that \(t_{xy}^{-}=\frac{1}{2}\bigl(\binom{n}{3}-t\bigr)\), which is invariant of choosing the vertices \(x,y\). Hence any pair of vertices of graph belong to the same number of 3-sets of \(\mathcal{G}\), thus \(\mathcal{G}\) is a regular two graph therefore the assertion follows by Lemma 3.2 and Proposition 3.1. \(\square\)
In the following, an example of a FSRSG on 6 vertices is provided. It is in fact Seidel’s favorite two-graph. He liked to call it the pentagon.
Example 3.6. The following set of 3-subsets is a regular two-graph on \(\{1,2,\ldots,6\}\). \[\{1,2,3\},\{1,2,4\},\{1,3,5\},\{1,4,6\},\{1,5,6\},\{2,3,6\},\{2,4,5\},\] \[\{2,5,6\},\{3,4,5\},\{3,4,6\}.\]
For the vertex 1 of the two-graph, the corresponding graph \(\Gamma_{1}\) is on the vertex set \(\{1,\ldots,6\}\) and the edges are \(23,24,35,46,56\). The corresponding signed complete graph is the following.
For two signed graphs \(\Sigma_{1}\), \(\Sigma_{2}\), we are curious on some conditions under which the signed graph \(\Sigma_{1}\times\Sigma_{2}\) is a SSRSG. This provides just a minor result.
Theorem 3.7. Let \(\Sigma_{1}\), \(\Sigma_{2}\) be two non-trivial signed graphs, then \(\Sigma_{1}\times\Sigma_{2}\) is a SSRSG if and only if \(\Sigma_{1}\), \(\Sigma_{2}\) are homogeneous complete signed graphs, that is all positive or all negative complete graphs. Moreover, \(K_{n}\times-K_{n}\) is a \(\operatorname{SSRSG}(n^{2},2n-2,n-2,2-n,2)\).
Proof. Let \(\Sigma_{1}=(\Gamma_{1},\sigma_{1})\), \(\Sigma_{2}=(\Gamma_{2},\sigma_{2})\), and \(\Sigma_{1}\times\Sigma_{2}=(\Gamma_{1}\times\Gamma_{2},\sigma)\) be their Cartesian product. Suppose that \(\Sigma_{1}\times\Sigma_{2}\) is a VSRSG with parameters \(\operatorname{VSRSG}(n,k,\rho_{0},t,\rho)\). Note that we have the following equalities for the degrees of vertices. \[d_{\Sigma_{1}\times\Sigma_{2}}(u,v) =d_{\Sigma_{1}}(u)+d_{\Sigma_{2}}(v).\]
Therefore, the graphs \(|\Sigma_{1}|\) and \(|\Sigma_{2}|\) must be regular. Now we claim that \(|\Sigma_{1}|\) (similarly \(|\Sigma_{2}|\)) is a complete graph. As contradiction, suppose that \(u_{i},u_{j}\) are two non-adjacent vertices in \(|\Sigma_{1}|\). Suppose \(x=(u_{i},v)\), \(y=(u_{j},w)\), \(v,w\in V_{|\Sigma_{2}|}\), \(v\ne w\), in this case, there exist no common neighbors between \(x,y\) in \(\Sigma_{1}\times\Sigma_{2}\), hence \(\rho\) must be 0. On the other hand if we set \(x=(u,v)\), \(y=(u’,v’)\), \(uu’\in E_{|\Sigma_{1}|}\), \(vv’\in E_{|\Sigma_{2}|}\), there exist two common neighbors of \(x,y\), that is \((u,v’)\) and \((u’,v)\). Thus we have the following: \[\begin{aligned} \rho={}&\sigma((u,v)(u,v’))\sigma((u,v’)(u’,v’))+\sigma((u,v)(u’,v))\sigma((u’,v)(u’,v’))\notag\\ ={}&2\sigma_{1}(uu’)\sigma_{2}(vv’), \end{aligned}\tag{3}\] but \(\rho\) was already equal to zero, which is impossible. This contradiction implies that \(|\Sigma_{1}|\), and similarly \(|\Sigma_{2}|\) is a complete graph. Note that (3) implies that the sign of all the edges in \(\Sigma_{1}\) and similarly \(\Sigma_{2}\) must be consistent, since otherwise the parameter \(\rho\) would take two different values. Hence the possible SSRSG’s would be \(K_{n}\times K_{n}\), or \(K_{n}\times-K_{n}\) as desired. \(\square\)
We would like to thank anonymous referee for her/his comments which improved appearance of this article. Moreover, we are grateful to Thomas Zaslavsky for his valuable comments which considerably improved the results.
The authors declare no conflict of interest.