ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 19 (2020) 83-93
https://doi.org/10.26493/1855-3974.2161.f55
(Also available at http://amc-journal.eu)
On sign-symmetric signed graphs*
Ebrahim Ghorbani
Department of Mathematics, K. N. Toosi University of Technology, P.O. Box 16765-3381, Tehran, Iran
Willem H. Haemers ©
Department of Econometrics and Operations Research, Tilburg University, Tilburg, The Netherlands
Hamid Reza Maimani , Leila Parsaei Majd * ©
Mathematics Section, Department ofBasic Sciences, Shahid Rajaee Teacher Training University, P.O. Box 16785-163, Tehran, Iran
Received 24 October 2019, accepted 27 March 2020, published online 10 November 2020
A signed graph is said to be sign-symmetric if it is switching isomorphic to its negation. Bipartite signed graphs are trivially sign-symmetric. We give new constructions of non-bipartite sign-symmetric signed graphs. Sign-symmetric signed graphs have a symmetric spectrum but not the other way around. We present constructions of signed graphs with symmetric spectra which are not sign-symmetric. This, in particular answers a problem posed by Belardo, Cioaba, Koolen, and Wang in 2018.
Keywords: Signed graph, spectrum. Math. Subj. Class. (2020): 05C22, 05C50
1 Introduction
Let G be a graph with vertex set V and edge set E. All graphs considered in this paper are undirected, finite, and simple (without loops or multiple edges).
A signed graph is a graph in which every edge has been declared positive or negative. In fact, a signed graph r is a pair (G, a), where G = (V, E) is a graph, called the underlying
* The authors would like to thank the anonymous referees for their helpful comments and suggestions. t Corresponding author.
E-mail addresses: ghorbani@kntu.ac.ir (Ebrahim Ghorbani), haemers@uvt.nl (Willem H. Haemers), maimani@ipm.ir (Hamid Reza Maimani), leila.parsaei84@yahoo.com (Leila Parsaei Majd)
©® This work is licensed under https://creativecommons.org/licenses/by/4.0/
Abstract
84
Ars Math. Contemp. 19 (2020) 125-145
graph, and a: E ^ {-1, +1} is the sign function or signature. Often, we write r = (G, a) to mean that the underlying graph is G. The signed graph (G, -a) = —r is called the negation of r. Note that if we consider a signed graph with all edges positive, we obtain an unsigned graph.
Let v be a vertex of a signed graph r. Switching at v is changing the signature of each edge incident with v to the opposite one. Let X C V. Switching a vertex set X means reversing the signs of all edges between X and its complement. Switching a set X has the same effect as switching all the vertices in X, one after another.
Two signed graphs r = (G, a) and r' = (G, a') are said to be switching equivalent if there is a series of switching that transforms r into r'. If r' is isomorphic to a switching of r, we say that r and r' are switching isomorphic and we write r ~ r'. The signed graph —r is obtained from r by reversing the sign of all edges. A signed graph r = (G, a) is said to be sign-symmetric if r is switching isomorphic to (G, —a), that is: r ~ —r.
For a signed graph r = (G, a), the adjacency matrix A = A(r) = (aj) is an n x n matrix in which a^ = a(vjvj) if vj and uj are adjacent, and 0 if they are not. Thus A is a symmetric matrix with entries 0, ±1 and zero diagonal, and conversely, any such matrix is the adjacency matrix of a signed graph. The spectrum of r is the list of eigenvalues of its adjacency matrix with their multiplicities. We say that r has a symmetric spectrum (with respect to the origin) if for each eigenvalue A of r, —A is also an eigenvalues of r with the same multiplicity.
Recall that (see [4]), the Seidel adjacency matrix of a graph G with the adjacency matrix A is the matrix S defined by
so that S = J — I — 2A. The Seidel adjacency spectrum of a graph is the spectrum of its Seidel adjacency matrix. If G is a graph of order n, then the Seidel matrix of G is the adjacency matrix of a signed complete graph r of order n where the edges of G are precisely the negative edges of r.
Proposition 1.1. Suppose S is a Seidel adjacency matrix of order n. If n is even, then S is nonsingular, and if n is odd, rank(S) > n — 1. In particular, if n is odd, and S has a symmetric spectrum, then S has an eigenvalue 0 of multiplicity 1.
Proof. We have det(S) = det(1 — J) (mod 2), and det(1 — J) = 1 — n. Hence, if n is even, det(S) is odd. So, S is nonsingular. Now, if n is odd, any principal submatrix of order n — 1 is nonsingular. Therefore, rank(S) > n — 1.	□
The goal of this paper is to study sign-symmetric signed graphs as well as signed graphs with symmetric spectra. It is known that bipartite signed graphs are sign-symmetric. We give new constructions of non-bipartite sign-symmetric graphs. It is obvious that sign-symmetric graphs have a symmetric spectrum but not the other way around (see Remark 4.1 below). We present constructions of graphs with symmetric spectra which are not sign-symmetric. This, in particular answers a problem posed in [2].
E. Ghorbani et al.: On sign-symmetric signed graphs
85
2 Constructions of sign-symmetric graphs
We note that the property that two signed graphs r and r' are switching isomorphic is equivalent to the existence of a 'signed' permutation matrix P such that PA(r)P-1 = A(r'). If r is a bipartite signed graph, then we may write its adjacency matrix as
It follows that PAP
1
A for
A
P
O B Bt O
-I O O I
which means that bipartite graphs are 'trivially' sign-symmetric. So it is natural to look for non-bipartite sign-symmetric graphs. The first construction was given in [1] as follows.
Theorem 2.1. Let n be an even positive integer and V1 and V2 be two disjoint sets of size n/2. Let G be an arbitrary graph with the vertex set V1. Construct the complement of G, that is Gc, with the vertex set V2. Assume that r = (Kn, a) is a signed complete graph in which E (G) U E (Gc) is the set of negative edges. Then r is sign-symmetric.
2.1 Constructions for general signed graphs
Let Mr,s denote the set of r x s matrices with entries from {-1,0,1}. We give another construction generalizing the one given in Theorem 2.1:
Theorem 2.2. Let B,C G Mk,k be symmetric matrices where B has a zero diagonal. Then the signed graph with the adjacency matrices
B C ' C -B
is sign-symmetric on 2k vertices.
Proof.
A
O	-I		B	C		OI		-B	-C
I	O		C	-B		-I O		-C	B
=A
□
Note that Theorem 2.2 shows that there exists a sign-symmetric graph for every even order.
We define the family F of signed graphs as those which have an adjacency matrix satisfying the conditions given in Theorem 2.2. To get an impression on what the role of F is in the family of sign-symmetric graphs, we investigate small complete signed graphs. All but one complete signed graphs with symmetric spectra of orders 4,6,8 are illustrated in Figure 1 (we show one signed graph in the switching class of the signed complete graphs induced by the negative edges). There is only one sign-symmetric complete signed graph of order 4. There are four complete signed graphs with symmetric spectrum of order 6, all of which are sign-symmetric, and twenty-one complete signed graphs with symmetric spectrum of order 8, all except the last one are sign-symmetric, and together with the negation of the last signed graph, Figure 1 gives all complete signed graphs with symmetric spectrum of order 4, 6 and 8. Interestingly, all of the above sign-symmetric signed graphs belong to F.
The following proposition shows that F is closed under switching.
86
Ars Math. Contemp. 19 (2020) 125-145
Figure 1: Complete signed graphs (up to switching isomorphism and negation) of order 4,6,8 having symmetric spectrum. The numbers next to the graphs are the non-negative eigenvalues. Only the last graph on the right is not sign-symmetric.
Proposition 2.3. If Y G F and r' is obtained from r by switching, then r' G F.
Proof. Let r G F .It is enough to show that if r' is obtained from r by switching with respect to its first vertex, then r' G F. We may write the adjacency matrix of r as follows:
A =
" 0	bT	c	cT
b	B'	c	C '
c	cT	0	-bT
c	C '	-b	-B'
After switching with respect to the first vertex of r, the adjacency matrix of the resulting
E. Ghorbani et al.: On sign-symmetric signed graphs	87
signed graph is
0	—bT	—c	—cT
-b	B'	c	C'
—c	cT	0	—bT
—c	C'	—b	—B'
Now by interchange the 1st and (k + 1)-th rows and columns we obtain
0	cT	—c	—bT
c	B'	—b	C'
—c	—bT	0	—cT
—b	C'	—c	—B'
which is a matrix of the form given in Theorem 2.2 and thus r' is isomorphic with a signed graph in F.	□
In the following we present two constructions for complete sign-symmetric signed graphs using self-complementary graphs.
2.2 Constructions for complete signed graphs
In the following, the meaning of a self-complementary graph is the same as defined for unsigned graphs. Let G be a self-complementary graph so that there is a permutation matrix P such that PA(G)P-1 = A(G) and PA(G)P-1 = A(G). It followsjhat if r is a complete signed graph with E(G) being its negative edges, then A(r) = A(G) - A(G) (in other words, A(r) is the Seidel matrix of G). It follows that PA(r)P-1 = -A(r). So we obtain the following:
88
Ars Math. Contemp. 19 (2020) 125-145
Observation 2.4. If r is a complete signed graph whose negative edges induce a self-complementary graph, then r is sign-symmetric.
We give one more construction of sign-symmetric signed graphs based on self-complementary graphs as a corollary to Observation 2.4. We remark that a self-complementary graph of order n exists whenever n = 0 or 1 (mod 4).
Proposition 2.5. Let G, H be two self-complementary graphs, and let r be a complete signed graph whose negative edges induce the join of G and H (or the disjoint union of G and H). Then r is sign symmetric. In particular, if G has n vertices, and if H is a singleton, then the complete signed graph r of order n +1 with negative edges equal to E(G) is sign-symmetric.
In the following remark we present a sign-symmetric construction for non-complete signed graphs.
Remark 2.6. Let r', T" be two signed graphs which are isomorphic to —r', —r'', respectively. Consider the signed graph r obtained from joining r' and r'' whose negative edges are the union of negative edges in r' and r''. Then, r is sign-symmetric.
Remark 2.7. By Proposition 2.5, we have a construction of sign-symmetric complete signed graphs of order n = 0,1 or 2 (mod 4). All complete sign-symmetric signed graphs of order 5 and 9 (depicted in Figure 2) can be obtained in this way. There is just one sign-symmetric signed graph of order 5 which is obtained by joining a vertex to a complete signed graph of order 4 whose negative edges form a path of length 3 (which is self-complementary). Moreover, there exist sixteen complete signed graphs of order 9 with symmetric spectrum of which ten are sign-symmetric; the first three are not sign-symmetric, and when we include their negations we get them all. All of these ten complete sign-symmetric signed graphs can be obtained by joining a vertex to a complete signed graph of order 8 whose negative edges induce a self-complementary graph. Note that there are exactly ten self-complementary graphs of order 8.
Theorem 2.8. There exists a complete sign-symmetric signed graph of order n if and only if n = 0,1 or 2 (mod 4).
Proof. Using the previous results obviously one can construct a sign-symmetric signed graph of order n whenever n = 0,1 or 2 (mod 4). Now, suppose that there is a complete sign-symmetric signed graph r of order n with n = 3 (mod 4). By [6, Corollary 3.6], the determinant of the Seidel matrix of r is congruent to 1 — n (mod 4). Since n = 3 (mod 4), the determinant of the Seidel matrix (obtained from the negative edges of r) is not zero. Hence, we can conclude that all eigenvalues of r are non-zero. Therefore, r cannot have a symmetric spectrum, and also it cannot be sign-symmetric.	□
In [7] all switching classes of Seidel matrices of order at most seven are given. There is a error in the spectrum of one of the graphs on six vertices in [7, Table 4.1] (2.37 should be 2.24), except for that, the results in [7] coincide with ours.
3 Positive and negative cycles
A graph whose connected components are K2 or cycles is called an elementary graph. Like unsigned graphs, the coefficients of the characteristic polynomial of the adjacency matrix of a signed graph r can be described in terms of elementary subgraphs of r.
E. Ghorbani et al.: On sign-symmetric signed graphs
89
Figure 2: Complete signed graphs (up to switching isomorphism and negation) of order 5,9 having symmetric spectrum. The numbers next to the graphs are the non-negative eigenvalues.The first three signed graphs of order 9 are not sign-symmetric.
Theorem 3.1 ([ , Theorem 2.3]). Let r = (G, a) be a signed graph and
Pr(x) = xn + a\xn-1 + • • • + an-ix + an	(3.1)
be the characteristic polynomial of the adjacency matrix of r. Then
a. = £ (-1)P(B)2|c(B)|a(B),
BeBi
where Bi is the set of elementary subgraphs of G on i vertices, p(B) is the number of components of B, c(B) the set of cycles in B, and a(B) = n cec(B) a(C).
Remark 3.2. It is clear that r has a symmetric spectrum if and only if in its characteristic polynomial (3.1), we have a2k+1 = 0, for k = 1, 2,....
In a signed graph, a cycle is called positive or negative if the product of the signs of its edges is positive or negative, respectively. We denote the number of positive and negative ^-cycles by c+ and c-, respectively.
90
Ars Math. Contemp. 19 (2020) 125-145
Observation 3.3. For sign-symmetric signed graph, we have
c2fc+1 — c2fc + 1 for k — 1 2,----
Remark 3.4. If in a signed graph r, c+fc+1 = c2fc+1 for all k = 1,2,..., then it is not necessary that r is sign-symmetric. See the complete signed graph given in Figure 5. For this complete signed graph we have c+fc+1 = c2-k+1 for all k = 1, 2,..., but it is not sign-symmetric. Moreover, one can find other examples among complete and non-complete signed graphs. For example, the signed graph given in Figure 4 is a non-complete signed graph with the property that c+k+1 = c-fc+1 for all k = 1, 2,..., but it is not sign-symmetric.
By Theorem 3.1, we have that a3 = 2(c- — c+). By Theorem 3.1 and Remark 3.2 for signed graphs having symmetric spectrum, we have c+ = c-. Further, for each complete signed graph with a symmetric spectrum, it can be seen that c+ = c-. However, the equality c+fc+1 = c-fc+1 does not necessarily hold for k > 3. The complete signed graph in Figure 3 has a symmetric spectrum for which c+ = c-.
Figure 3: The graph induced by negative edges of a complete signed graph on 9 vertices with a symmetric spectrum but c+ = c-.
Remark 3.5. There are some examples showing that for a non-complete signed graph we have c+k+1 = c-fc+1 for all k = 1, 2,..., but their spectra are not symmetric. As an example see Figure 4 (dashed edges are negative; solid edges are positive).
Now, we may ask a weaker version of the result mentioned in Remark 3.4 as follows.
Question 3.6. Is it true that if in a complete signed graph r, c 1,2,..., then r has a symmetric spectrum?
2
2k+1
C2fc+i for k
4 Sign-symmetric vs. symmetric spectrum
Remark 4.1. Consider the complete signed graph whose negative edges induces the graph of Figure 5. This graph has a symmetric spectrum, but it is not sign-symmetric. Note that this complete signed graph has the minimum order with this property. Moreover, for this complete signed graph we have the equalities c+fc+1 = c-fc+1 for k = 1, 2,3.
E. Ghorbani et al.: On sign-symmetric signed graphs
91
Figure 4: A signed graph with c+k+1 = c2k+1 for k = 1, 2,..., but its spectrum is not symmetric.
Figure 5: The graph induced by negative edges of a complete signed graph on 8 vertices with a symmetric spectrum but not sign-symmetric.
Remark 4.2. A conference matrix C of order n is an n x n matrix with zero diagonal and all off-diagonal entries ±1, which satisfies CCT = (n - 1)1. If C is symmetric, then C has eigenvalues ±\Jn — 1. Hence, its spectrum is symmetric. Conference matrices are well-studied; see for example [4, Section 10.4]. An important example of a symmetric conference matrix is the Seidel matrix of the Paley graph extended with an isolated vertex, where the Paley graph is defined on the elements of a finite field Fq, with q = 1 (mod 4), where two elements are adjacent whenever the difference is a nonzero square in Fq. The Paley graph is self-complementary. Therefore, by Proposition 2.5, C is the adjacency matrix of a sign-symmetric complete signed graph. However, there exist many more symmetric conference matrices, including several that are not sign-symmetric (see [5]).
In [2], the authors posed the following problem on the existence of the non-complete signed graphs which are not sign-symmetric but have symmetric spectrum.
Problem 4.3 ([2]). Are there non-complete connected signed graphs whose spectrum is symmetric with respect to the origin but they are not sign-symmetric?
We answer this problem by showing that there exists such a graph for any order n > 6. For s > 0, define the signed graph rs to be the graph illustrated in Figure 6.
Theorem 4.4. For s > 0, the graph rs has a symmetric spectrum, but it is not sign-symmetric.
Proof. Let S be the set of s vertices adjacent to both 1 and 5. The positive 5-cycles of rs are 123461 together with u1645u for any u G S, and the negative 5-cycles are u1465u for
93
Ars Math. Contemp. 19 (2020) 125-145
Figure 6: The graph rs.
any u G S. Hence, c+ = s + 1 and c- = s. In view of Observation 3.3, this shows that rs is not sign-symmetric.
Next, we show that rs has a symmetric spectrum. It suffices to verify that a2k+1 = 0 for k = 1,2,....
The graph rs contains a unique positive cycle of length 3: 4564 and a unique negative cycle of length 3: 1461. It follows that a3 = 0.
As discussed above, we have c+ = s + 1 and c- = s. We count the number of positive and negative copies of K2 U C3. For the negative triangle 1461, there are s + 1 non-incident edges, namely 23 and 5u for any u G S and for the positive triangle 4564, there are s + 2 non-incident edges, namely 12, 23 and 1u for any u G S. It follows that
as = —2((s +1) - s) + 2((s + 2) - (s + 1) = 0. Now, we count the number of positive and negative elementary subgraphs on 7 vertices: C7: s positive: u123465u for any u G S, and no negative; K2 U C5 : 2s positive: u5 U 123461, and 23 U u1645u for any u G S, and s negative: 23 U u1465u for any u G S; 2K2 U C3: s +1 positive: u1 U 23 U 4564 for any u G S, and s +1 negative: u5 U 23 U 1461 for any u G S;
C4 U C3: none. Therefore,
a7 = —2(s — 0) + 2(2s — s) — 2((s +1) — (s + 1)) = 0.
The graph rs contains no elementary subgraph on 8 vertices or more. The result now follows.	□
More families of non-complete signed graphs with a symmetric spectrum but not sign-symmetric can be found. Consider the signed graphs rs,t depicted in Figure 7, in which the number of upper repeated pair of vertices is s > 0 and the number of upper repeated pair of vertices is t > 1. In a similar fashion as in the proof of Theorem 4.4 it can be verified that rs t has a symmetric spectrum, but it is not sign-symmetric.
3
E. Ghorbani et al.: On sign-symmetric signed graphs	89
ORCID iDs
Willem H. Haemers © https://orcid.org/0000-0001-7308-8355 Hamid Reza Maimani © https://orcid.org/0000-0001-9020-0871 Leila Parsaei Majd © https://orcid.org/0000-0003-0775-3147
References
[1]	S. Akbari, H. R. Maimani and L. Parsaei Majd, On the spectrum of some signed complete and complete bipartite graphs, Filomat 32 (2018), 5817-5826, doi:10.2298/fil1817817a.
[2]	F. Belardo, S. M. Cioaba, J. Koolen and J. Wang, Open problems in the spectral theory of signed graphs, Art Discrete Appl. Math. 1 (2018), #P2.10 (23 pages), doi:10.26493/2590-9770.1286. d7b.
[3]	F. Belardo and S. K. Simic, On the Laplacian coefficients of signed graphs, Linear Algebra Appl. 475 (2015), 94-113, doi:10.1016/j.laa.2015.02.007.
[4]	A. E. Brouwer and W. H. Haemers, Spectra of Graphs, Universitext, Springer, New York, 2012, doi:10.1007/978-1-4614-1939-6.
[5]	F. C. Bussemaker, R. A. Mathon and J. J. Seidel, Tables of two-graphs, in: S. B. Rao (ed.), Combinatorics and Graph Theory, Springer, Berlin-New York, volume 885 of Lecture Notes in Mathematics, 1981 pp. 70-112, proceedings of the Second Symposium held at the Indian Statistical Institute, Calcutta, February 25 - 29, 1980.
[6]	G. Greaves, J. H. Koolen, A. Munemasa and F. Szollosi, Equiangular lines in Euclidean spaces, J. Comb. Theory Ser. A 138 (2016), 208-235, doi:10.1016/j.jcta.2015.09.008.
[7]	J. H. van Lint and J. J. Seidel, Equilateral point sets in elliptic geometry, Nederl. Akad. Wetensch. Proc. Ser. A 69 (1966), 335-348.