© Wuhan University 2022

0 Introduction

In this paper we only consider finite and undirected graphs without loops or multiple edges. Let $\mathrm{\Gamma }$ be a group and $S=S^{-\mathrm{1}}$ is a non-empty subset which does not contain the identity element 1 of $\mathrm{\Gamma }$. The Cayley graph^[1]$\mathrm{C}\mathrm{a}\mathrm{y}(\mathrm{\Gamma },S)$ is a graph having vertex set $\mathrm{\Gamma }$ and edge set $\{\{v,vs\}:v\in \mathrm{\Gamma },s\in S\}$. For further information about Cayley graphs, one may refer to Refs.[2,3].

In 1990, unitary addition Cayley graph^[4]$G_n=$$\mathrm{C}\mathrm{a}{\mathrm{y}}^{+}(Z_n,U_n)$ was first introduced. For a positive integer $n>\mathrm{1}$, $G_n$ is the graph whose vertex set is $Z_n$, and $Z_n$ is the ring of integers modulo $n$. If $U_n$ denotes set of all its units, then two vertices $a$ and $b$ are adjacent if and only if $a+b\in U_n$. Note that $G_n$ is $|U_n|$-regular if $|Z_n|$ is even and $(|U_n|,|U_n|-\mathrm{1})$-semiregular if $|Z_n|$ is odd^[5]. Some examples of $G_n=\mathrm{C}\mathrm{a}{\mathrm{y}}^{+}(Z_n,U_n)$ are illustrated in Fig. 1.

Fig. 1 Some examples of addition Cayley graphs

1 Preliminaries

1.1 Signed Graphs and Some Derived Graphs

Harary^[6] introduced the definition of signed graphs in connection with the study of the theory of social balance, which can also be written as s-graphs^[7] or sigraphs^[8]. Signed graphs arose from the fact that psychologists used square matrices with elements -1, 0, and 1 to represent disliking, indifference and liking, respectively. It also can be depicted by a graph with positive and negative lines. Formally, a signed graph is an ordered pair $\Sigma =(G,\sigma )$, where $G=(V(G),E(G))$ is the underlying graph of $\Sigma$ and $\sigma :E(G)\to \{+\mathrm{1},-\mathrm{1}\}$ is a signature function from the edge set $E(G)$ into the set of $\{+\mathrm{1},-\mathrm{1}\}$.

For an arbitrary edge $e$ of $\Sigma$, if $\sigma (e)=+\mathrm{1}(-\mathrm{1})$ then it is called positive (negative) edge. Moreover, $\Sigma$ is said to be all-positive (all-negative) if all edges are positive (negative). Furthermore, $\Sigma$ is also said to be homogeneous if it is either all-positive or all-negative and heterogeneous otherwise. The positive (negative) degree of a vertex $v\in V(G)$ denoted by $d^{+}(v)(d^{-}(v))$ which is the number of positive (negative) edges associates to $v$ and the degree of $v$ is $d(v)=d^{+}(v)+d^{-}(v)$. Based on these concepts, in what follows some derived graphs of $\Sigma$ are introduced.

In 1957, Harary introduced the negation^[9]$\eta (\Sigma )$ of signed graphs $\Sigma$ which is obtained from $\Sigma$ by negating the sign of every edge.

In 1969, Behzad and Chartrand defined line-sigraphs^[7]$L(\Sigma )$ of signed graphs $\Sigma$ as the sigraph whose points can be put in one-to-one correspondence with the lines of $\Sigma$ in such a way that two points of $L(\Sigma )$ are joined by a negative line if and only if they correspond to two adjacent negative lines of $\Sigma$ and are joined by a positive line if they correspond to some other two adjacent lines of $\Sigma$.

In 2006, Acharya and Sinha came up with common-edge sigraphs^[8]$C_E(\Sigma )$. Given a sigraph $\Sigma$, its common-edge sigraph $C_E(\Sigma )$ is a sigraph whose vertex-set is the set of pairs of adjacent edges in $\Sigma$ and two vertices of $C_E(\Sigma )$ are adjacent if and only if the corresponding pairs of adjacent edges of $\Sigma$ have exactly one edge in common, with the same sign as that of their common edge.

An example of one signed graph and its three derived graphs is shown in Fig. 2. It should be noted that negative edges are represented by dash lines and positive edges by straight lines here and in the rest figures.

Fig. 2 The example of signed graphs and its derived graphs

Motivated by Iranmanesh and Moghaddami^[10], in this paper, we will investigate some properties of an addition Cayley signed graph $\Sigma$ which is defined as follows.

Definition 1   Let $G=\mathrm{C}\mathrm{a}{\mathrm{y}}^{+}(Z_{p_{\mathrm{1}}}\times Z_{p_{\mathrm{1}}^{{\alpha }_{\mathrm{1}}}{p}_{\mathrm{2}}^{{\alpha }_{\mathrm{2}}}\cdots p_k^{{\alpha }_k}},\Phi )$ be a simple graph having vertex set $V(G)=Z_{p_{\mathrm{1}}}\times Z_{p_{\mathrm{1}}^{{\alpha }_{\mathrm{1}}}{p}_{\mathrm{2}}^{{\alpha }_{\mathrm{2}}}\cdots p_k^{{\alpha }_k}}$ and edge set $E(G)=\{\{x,y\}:x+y\in \Phi \}$, where all $p_{\mathrm{1}},p_{\mathrm{2}},$$\cdots ,p_k$ are distinct prime factors and $\Phi$ is the set of all units of the ring $Z_{p_{\mathrm{1}}}\times Z_{p_{\mathrm{1}}^{{\alpha }_{\mathrm{1}}}{p}_{\mathrm{2}}^{{\alpha }_{\mathrm{2}}}\cdots p_k^{{\alpha }_k}}$. Let $\Sigma =(G,\sigma )$ be a signed graph whose underlying graph is $G$ and signature function is $\sigma :E(G)\to \{+\mathrm{1},-\mathrm{1}\}$ defined as^[11]

$\sigma (\{x,y\})=\{\begin{array}{cc}+\mathrm{1},& \mathrm{i}\mathrm{f}x\in \phi (p_{\mathrm{1}})\mathrm{o}\mathrm{r}y\in \phi (p_{\mathrm{1}}^{{\alpha }_{\mathrm{1}}}{p}_{\mathrm{2}}^{{\alpha }_{\mathrm{2}}}\cdots p_k^{{\alpha }_k});\\ -\mathrm{1},& \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}.\end{array}$

Examples $\Sigma =(\mathrm{C}\mathrm{a}{\mathrm{y}}^{+}(Z_{\mathrm{2}}\times Z_{\mathrm{2}\times \mathrm{3}},\Phi ),\sigma )$ and ${\Sigma }^{\text{'}}$$=(\mathrm{C}\mathrm{a}{\mathrm{y}}^{+}(Z_{\mathrm{3}}\times Z_{\mathrm{2}\times \mathrm{3}},\Phi ),\sigma )$ are displayed in Fig. 3 and 4, respectively.

Fig. 3 $\mathit{\Sigma }=(\mathbf{C}\mathbf{a}{\mathbf{y}}^{+}({\mathit{Z}}_{\mathrm{2}}\times {\mathit{Z}}_{\mathrm{2}\times \mathrm{3}},\mathit{\Phi }),\mathit{\sigma })$

Fig. 4 ${\mathit{\Sigma }}^{\mathit{\text{'}}}=(\mathbf{C}\mathbf{a}{\mathbf{y}}^{+}({\mathit{Z}}_{\mathrm{3}}\times {\mathit{Z}}_{\mathrm{2}\times \mathrm{3}},\mathit{\Phi }),\mathit{\sigma })$

1.2 The Notion of Balance in a Signed Graph

As we all known that a positive cycle of a signed graph is the one in which the number of negative lines is even, while a negative cycle is not positive^[6]. In other words, a cycle in a signed graph is positive if it contains an even number of negative edges. An exact formula about signs for an arbitrary cycle $C$ is given by $\sigma (C)={\prod }_{e\in C}(\sigma (e))$ , where $e\in C$^[12].

Definition 2^[6] A signed graph is said to be balanced if all its cycles are positive.

1.3 The Notion of Clustering in a Signed Graph

Definition 3^[13] A clustering of a signed graph is a partition of the point set into subsets $P_{\mathrm{1}},P_{\mathrm{2}},\cdots ,P_n$ (called plus-sets or Davis partitions) such that each positive line joins two points in the same subset and each negative line joins two points from different subsets.

Lemma 1^[13] A signed graph has a clustering if and only if it contains no cycle having exactly one negative line.

1.4 The Notion of Sign-Compatibility in a Signed Graph

As known that a simple graph $G_{\mathrm{1}}=(V_{\mathrm{1}},E_{\mathrm{1}})$ is said to be isomorphic to $G_{\mathrm{2}}=(V_{\mathrm{2}},E_{\mathrm{2}})$ if and only if there is a bijective $f:V_{\mathrm{1}}\to V_{\mathrm{2}}$ satisfied with $\{v_{\mathrm{1}},v_{\mathrm{2}}\}\in E_{\mathrm{1}}\iff$$\{f(v_{\mathrm{1}}),f(v_{\mathrm{2}})\}\in E_{\mathrm{2}}$ for $v_{\mathrm{1}},v_{\mathrm{2}}\in V_{\mathrm{1}}$. Analogously, ${\Sigma }_{\mathrm{1}}$ and ${\Sigma }_{\mathrm{2}}$ are isomorphic if and only if there is an isomorphic mapping between the two underlying graphs that maintains edge signatures.

Lemma 2^[14] A sigraph $\Sigma$ is sign-compatible if and only if $\Sigma$ does not contain a sub-sigraph isomorphic to either of the two sigraphs, $S_{\mathrm{1}}$ formed by taking the path $P_{\mathrm{4}}=(x,u,v,y)$ with both edges $\{x,u\}$ and $\{v,y\}$ negative and the edge $\{u,v\}$ positive and $S_{\mathrm{2}}$ formed by taking $S_{\mathrm{1}}$ and identifying the vertices $x$ and $y$ (see Fig. 5).

Fig. 5 Forbidden subsigraphs for a sign-compatible sigraph

The rest of this paper is organized as follows. In Section 2, we describe the balanced addition Cayley signed graphs. In Section 3, we prove some results about clusterability and sign-compatibility.

2 Balance in $\mathit{\Sigma }$ and Derived Graphs

In this section, we discuss the balance of $\Sigma =(G,\sigma )$ and its derived graphs $\eta (\Sigma )$, $L(\Sigma )$ and $C_E(\Sigma )$, where $G=\mathrm{C}\mathrm{a}{\mathrm{y}}^{+}(Z_{p_{\mathrm{1}}}\times Z_{p_{\mathrm{1}}^{{\alpha }_{\mathrm{1}}}{p}_{\mathrm{2}}^{{\alpha }_{\mathrm{2}}}\cdots p_k^{{\alpha }_k}},\Phi )$ and $p_{\mathrm{1}},p_{\mathrm{2}},\cdots ,p_k$ are distinct prime factors. Firstly, we give equivalent condition for the balanced addition Cayley signed graphs.

Lemma 3^[15] Two signed graphs on the same und- erlying graph are switching equivalent if and only if they have the same list of balanced circles.

For any positive integer $n$, let $\phi (n)=\{l:\mathrm{1}\le l<n,$$\mathrm{g}\mathrm{c}\mathrm{d}(l,n)=\mathrm{1}\}$.

Lemma 4   Let $\Sigma =(G,\sigma )$ be an addition Cayley signed graph, where $G=\mathrm{C}\mathrm{a}{\mathrm{y}}^{+}(Z_{p_{\mathrm{1}}}\times Z_{p_{\mathrm{1}}^{{\alpha }_{\mathrm{1}}}{p}_{\mathrm{2}}^{{\alpha }_{\mathrm{2}}}\cdots p_k^{{\alpha }_k}},\Phi )$ and all $p_{\mathrm{1}},p_{\mathrm{2}},\cdots ,p_k$ are distinct prime factors. If one of $p_{\mathrm{1}},p_{\mathrm{2}},\cdots ,p_k$ is 2, then $\Sigma$ has exactly $|\Phi {|}^{\mathrm{2}}$ positive edges.

Proof   Since one of the prime factors is 2 then there are two following cases.

Case 1 Suppose $p_{\mathrm{1}}=\mathrm{2}$. In this case, $\Sigma$ is disco- nnected and has exactly two connected components ${\Sigma }_{\mathrm{1}}=(G_{\mathrm{1}},\sigma )$ with vertex set $V({\Sigma }_{\mathrm{1}})=\{(u,v):u=\mathrm{1}\mathrm{a}\mathrm{n}\mathrm{d}$$v\mathrm{i}\mathrm{s}\mathrm{o}\mathrm{d}\mathrm{d}\}\bigcup \{(u,v):u=\mathrm{0}\mathrm{a}\mathrm{n}\mathrm{d}v\mathrm{i}\mathrm{s}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}\}$ and ${\Sigma }_{\mathrm{2}}=(G_{\mathrm{2}},$$\sigma )$ with vertex set $V({\Sigma }_{\mathrm{2}})=\{(u,v):u=\mathrm{0}\mathrm{a}\mathrm{n}\mathrm{d}v\mathrm{i}\mathrm{s}\mathrm{o}\mathrm{d}\mathrm{d}\}\bigcup \{(u,v):u=\mathrm{1}\mathrm{a}\mathrm{n}\mathrm{d}v\mathrm{i}\mathrm{s}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}\}$.

Note that the underlying graph $G$ of $\Sigma$ is a $|\Phi |$ -regular graph. Hence,

$|E({\Sigma }_{\mathrm{1}})|=|E({\Sigma }_{\mathrm{2}})|=\frac{\mathrm{1}}{\mathrm{2}}|E(\Sigma )|=\frac{\mathrm{1}}{\mathrm{2}}|E(G)|=\frac{\mathrm{1}}{\mathrm{4}}|\Phi |p_{\mathrm{1}}^{{\alpha }_{\mathrm{1}}+\mathrm{1}}{p}_{\mathrm{2}}^{{\alpha }_{\mathrm{2}}}\cdots p_k^{{\alpha }_k}$

Assume $\{(u,v),(u^{\text{'}},v^{\text{'}})\}$ is an arbitrary edge in ${\Sigma }_{\mathrm{1}}$, where $(u,v)\in \{(u,v):u=\mathrm{1}\mathrm{a}\mathrm{n}\mathrm{d}v\mathrm{i}\mathrm{s}\mathrm{o}\mathrm{d}\mathrm{d}\}$, $(u^{\text{'}},v^{\text{'}})\in \{$$(u,v):u=\mathrm{0}\mathrm{a}\mathrm{n}\mathrm{d}v\mathrm{i}\mathrm{s}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}\}$ and $v+v^{\text{'}}\in \phi (p_{\mathrm{1}}^{{\alpha }_{\mathrm{1}}}{p}_{\mathrm{2}}^{{\alpha }_{\mathrm{2}}}\cdots$$p_k^{{\alpha }_k})$. By Definition 1, $\{(u,v),(u^{\text{'}},v^{\text{'}})\}$ is positive edge if and only if $(u,v)\in \Phi$ since $\Phi \subseteq \{(u,v):u=\mathrm{1}\mathrm{a}\mathrm{n}\mathrm{d}v$$\mathrm{i}\mathrm{s}\mathrm{o}\mathrm{d}\mathrm{d}\}$ and $\{(u,v):u=\mathrm{0}\mathrm{a}\mathrm{n}\mathrm{d}v\mathrm{i}\mathrm{s}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}\}\bigcap \Phi =\mathrm{\varnothing }$. Moreover, if $(u,v)\in \{(u,v):u=\mathrm{1}\mathrm{a}\mathrm{n}\mathrm{d}v\mathrm{i}\mathrm{s}\mathrm{o}\mathrm{d}\mathrm{d}\}\backslash \Phi$ then this edge is negative. Therefore ${\Sigma }_{\mathrm{1}}$ has exactly $|\Phi {|}^{\mathrm{2}}$ positive edges.

For any edge $\{(u,v),(u^{\text{'}},v^{\text{'}})\}\in E({\Sigma }_{\mathrm{2}})$, where $(u,v)\in$$\{(u,v):u=\mathrm{0}\mathrm{a}\mathrm{n}\mathrm{d}v\mathrm{i}\mathrm{s}\mathrm{o}\mathrm{d}\mathrm{d}\}$, $(u^{\text{'}},v^{\text{'}})\in \{(u,v):u=\mathrm{1}\mathrm{a}\mathrm{n}\mathrm{d}v\mathrm{i}\mathrm{s}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}\}$ and $v+v^{\text{'}}\in \phi (p_{\mathrm{1}}^{{\alpha }_{\mathrm{1}}}{p}_{\mathrm{2}}^{{\alpha }_{\mathrm{2}}}\cdots p_k^{{\alpha }_k})$. Obviously, all members of $V({\Sigma }_{\mathrm{2}})$ are not in $\Phi$ and all edges in ${\Sigma }_{\mathrm{2}}$ are negative.

Case 2 Suppose $p_{\mathrm{1}}\ge \mathrm{3}$ and $\exists p_i=\mathrm{2}$ for $i\in \{\mathrm{2},$$\mathrm{3},\cdots ,k\}$. It is not difficult to see that $\Sigma$ is connected. The vertex $(\mathrm{0,0})$ is adjacent to all members of $\Phi$, and each member of $\Phi$ is adjacent to other $|\Phi |-\mathrm{1}$ vertices of $\Sigma$. Moreover, those edges have at least one vertex in $\Phi$. So there are $|\Phi |+|\Phi |(|\Phi |-\mathrm{1})=|\Phi {|}^{\mathrm{2}}$ positive edges. Let

$V_{\mathrm{1}}=\{(u,v):u=\mathrm{0}\mathrm{a}\mathrm{n}\mathrm{d}v\mathrm{i}\mathrm{s}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}\}\bigcup \{(u,v):u\in \{\mathrm{1,2},\cdots ,p_{\mathrm{1}}-\mathrm{1}\}\mathrm{a}\mathrm{n}\mathrm{d}v\mathrm{i}\mathrm{s}\mathrm{n}\mathrm{o}\mathrm{t}\mathrm{o}\mathrm{d}\mathrm{d}-\mathrm{m}\mathrm{u}\mathrm{l}\mathrm{t}\mathrm{i}\mathrm{p}\mathrm{l}\mathrm{e}\mathrm{o}\mathrm{f}\mathrm{p}\mathrm{r}\mathrm{i}\mathrm{m}\mathrm{e}\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{s}\};$

$V_{\mathrm{2}}=\{(u,v):u=\mathrm{0}\mathrm{a}\mathrm{n}\mathrm{d}v\mathrm{i}\mathrm{s}\mathrm{o}\mathrm{d}\mathrm{d}\}\bigcup \{(u,v):u\in \{\mathrm{1,2},\cdots ,p_{\mathrm{1}}-\mathrm{1}\}\mathrm{a}\mathrm{n}\mathrm{d}v\mathrm{i}\mathrm{s}\mathrm{o}\mathrm{d}\mathrm{d}-\mathrm{m}\mathrm{u}\mathrm{l}\mathrm{t}\mathrm{i}\mathrm{p}\mathrm{l}\mathrm{e}\mathrm{o}\mathrm{f}\mathrm{p}\mathrm{r}\mathrm{i}\mathrm{m}\mathrm{e}\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{s}\}.$

Let $V=V_{\mathrm{1}}\bigcup V_{\mathrm{2}}$. Assume $(u,v)$ and $(u^{\text{'}},v^{\text{'}})$ are arbitrary vertices of $V_{\mathrm{2}}$, the sum of $v$ and $v^{\text{'}}$ is even since $v$ and $v^{\text{'}}$ are both odd, hence $(u,v)+(u^{\text{'}},v^{\text{'}})\notin \Phi$. Thus none of $V_{\mathrm{2}}$ are adjacent to each other. Each vertex of $V_{\mathrm{2}}$ is adjacent to one of the vertices of $V_{\mathrm{1}}$ since $\Sigma$ is connected. Let $(u,v)\in V_{\mathrm{1}}$ be adjacent to $(u^{\text{'}},v^{\text{'}})\in V_{\mathrm{2}}$. $v$ should be even since $v^{\text{'}}$ is odd. We have $(u,v)\notin \Phi$ and all vertices of $V_{\mathrm{2}}$ are not in $\Phi$. All edges incident with the vertices of $V_{\mathrm{2}}$ are negative and the number is

$|V_{\mathrm{2}}|\times |\Phi |=\frac{|V(\Sigma )|}{\mathrm{2}}|\Phi |-|\Phi {|}^{\mathrm{2}}$

where $|V(\Sigma )|=p_{\mathrm{1}}^{{\alpha }_{\mathrm{1}}+\mathrm{1}}{p}_{\mathrm{2}}^{{\alpha }_{\mathrm{2}}}\cdots p_k^{{\alpha }_k}$.

The following theorem gives an equivalent charact- erization for $\Sigma$ being balanced.

Theorem 1   Let $\Sigma =(G,\sigma )$ be an addition Cayley signed graph, where $G=\mathrm{C}\mathrm{a}{\mathrm{y}}^{+}(Z_{p_{\mathrm{1}}}\times Z_{p_{\mathrm{1}}^{{\alpha }_{\mathrm{1}}}{p}_{\mathrm{2}}^{{\alpha }_{\mathrm{2}}}\cdots p_k^{{\alpha }_k}},\Phi )$ and all $p_{\mathrm{1}},p_{\mathrm{2}},\cdots ,p_k$ are distinct prime factors. Then $\Sigma$ is balanced if and only if one of the prime factors is 2.

Proof  

Necessity: Contrarily, assume $p_i\ge \mathrm{3}$ for any $i=\mathrm{1,2},\cdots ,k$. In this case, $\Sigma$ is connected. Moreover, the numbers 1 and 2 are both in $\phi (p_{\mathrm{1}})$ and $\phi (p_{\mathrm{1}}^{{\alpha }_{\mathrm{1}}}{p}_{\mathrm{2}}^{{\alpha }_{\mathrm{2}}}\cdots p_k^{{\alpha }_k})$. Let us consider a cycle $C=((\mathrm{0,1}),$$(\mathrm{1,0}),(\mathrm{1,1}),(\mathrm{0,1}))$ in $\Sigma$. In fact, $(\mathrm{0,1})+(\mathrm{1,0})=(\mathrm{1,1})\in \Phi$, the vertex $(\mathrm{0,1})$ is adjacent to $(\mathrm{1,0})$. Also, $(\mathrm{1,0})$ is adjacent to $(\mathrm{1,1})$ since $(\mathrm{1,0})+(\mathrm{1,1})=(\mathrm{2,1})\in \Phi$. The vertex $(\mathrm{1,1})$ is adjacent to $(\mathrm{0,1})$ since $(\mathrm{1,1})+(\mathrm{0,1})=$$(\mathrm{1,2})\in \Phi$. Note that $(\mathrm{0,1})\notin \Phi ,[(\mathrm{1,0})\notin \Phi ]$ and $(\mathrm{1,1})\in \Phi$, we have $\sigma (\{(\mathrm{0,1}),(\mathrm{1,0})\})$$=-\mathrm{1}$, $\sigma (\{(\mathrm{1,0}),(\mathrm{1,1})\})=+\mathrm{1}$, $\sigma (\{(\mathrm{1,1}),(\mathrm{0,1})\})=+\mathrm{1}$. Then the cycle $C$ is not positive and thus $\Sigma$ is unbalanced. This is a contradiction.

Sufficiency: Suppose one of the prime factors is 2.

Case 1 Assume $p_{\mathrm{1}}=\mathrm{2}$. Then by the proof of Lemma 4 it is known that $\Sigma$ is disconnected and has exactly two connected components ${\Sigma }_{\mathrm{1}}=(G_{\mathrm{1}},\sigma )$ with vertex set $V({\Sigma }_{\mathrm{1}})=$$\{(u,v):u=\mathrm{1}\mathrm{a}\mathrm{n}\mathrm{d}v\mathrm{i}\mathrm{s}\mathrm{o}\mathrm{d}\mathrm{d}\}\bigcup \{(u,v):u=\mathrm{0}\mathrm{a}\mathrm{n}\mathrm{d}$$v\mathrm{i}\mathrm{s}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}\}$ and ${\Sigma }_{\mathrm{2}}=(G_{\mathrm{2}},\sigma )$ with vertex set $V({\Sigma }_{\mathrm{2}})=\{(u,v):u=\mathrm{0}\mathrm{a}\mathrm{n}\mathrm{d}$$v\mathrm{i}\mathrm{s}\mathrm{o}\mathrm{d}\mathrm{d}\}\bigcup \{(u,v):u=\mathrm{1}\mathrm{a}\mathrm{n}\mathrm{d}v$$\mathrm{i}\mathrm{s}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}\}$.

For ${\Sigma }_{\mathrm{2}}$, all edges are negative since $V({\Sigma }_{\mathrm{2}})\bigcap \Phi =$$\mathrm{\varnothing }$. Next we prove that every cycle in ${\Sigma }_{\mathrm{2}}$ is positive. Suppose $C^{\text{'}}=(x_{\mathrm{1}},x_{\mathrm{2}},x_{\mathrm{3}},\cdots ,x_m,x_{\mathrm{1}})$ is an arbitrary cycle in ${\Sigma }_{\mathrm{2}}$. Without loss of generality, assume that $x_{\mathrm{1}}\in$$\{(u,v):u=\mathrm{0}\mathrm{a}\mathrm{n}\mathrm{d}v\mathrm{i}\mathrm{s}\mathrm{o}\mathrm{d}\mathrm{d}\}$. By Definition 1, we have $x_{\mathrm{2}}$ and $x_m$ both in $\{(u,v):u=\mathrm{1}\mathrm{a}\mathrm{n}\mathrm{d}v\mathrm{i}\mathrm{s}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}\}$. Similarly, the vertices that are adjacent to $x_{\mathrm{2}}$ and $x_m$ are in $\{(u,v):u=\mathrm{0}\mathrm{a}\mathrm{n}\mathrm{d}v\mathrm{i}\mathrm{s}\mathrm{o}\mathrm{d}\mathrm{d}\}$. By continuing this process, it is easy to see that $C^{\text{'}}$ contains an even number of negative edges. Thus ${\Sigma }_{\mathrm{2}}$ is balanced.

For ${\Sigma }_{\mathrm{1}}$, let us consider an arbitrary cycle $C^{″}=$$({x_{\mathrm{1}}}^{\mathrm{\text{'}}},{x_{\mathrm{2}}}^{\mathrm{\text{'}}},{x_{\mathrm{3}}}^{\mathrm{\text{'}}},\cdots ,{x_m}^{\mathrm{\text{'}}},{x_{\mathrm{1}}}^{\mathrm{\text{'}}})$. Note that every edge in ${\Sigma }_{\mathrm{1}}$ has one vertex in $\{(u,v):u=\mathrm{0}\mathrm{a}\mathrm{n}\mathrm{d}v\mathrm{i}\mathrm{s}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}\}$ and the other in $\{(u,v):u=\mathrm{1}\mathrm{a}\mathrm{n}\mathrm{d}v\mathrm{i}\mathrm{s}\mathrm{o}\mathrm{d}\mathrm{d}\}$. Without loss of generality, assume that ${x_{\mathrm{1}}}^{\mathrm{\text{'}}}\in \{(u,v):u=\mathrm{0}\mathrm{a}\mathrm{n}\mathrm{d}v\mathrm{i}\mathrm{s}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}\}$ then ${x_{\mathrm{2}}}^{\mathrm{\text{'}}}\in \{(u,v):u=\mathrm{1}\mathrm{a}\mathrm{n}\mathrm{d}v\mathrm{i}\mathrm{s}\mathrm{o}\mathrm{d}\mathrm{d}\}$ and ${x_{\mathrm{3}}}^{\mathrm{\text{'}}}\in \{(u,v):u=\mathrm{0}\mathrm{a}\mathrm{n}\mathrm{d}v\mathrm{i}\mathrm{s}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}\}$. Obviously, $\{(u,v):u=\mathrm{0}\mathrm{a}\mathrm{n}\mathrm{d}v\mathrm{i}\mathrm{s}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}\}$$\bigcap \Phi =\mathrm{\varnothing }$. There are two following cases. If ${x_{\mathrm{2}}}^{\mathrm{\text{'}}}\in \Phi$, then $\{{x_{\mathrm{1}}}^{\mathrm{\text{'}}},{x_{\mathrm{2}}}^{\mathrm{\text{'}}}\}$ and $\{{x_{\mathrm{2}}}^{\mathrm{\text{'}}},{x_{\mathrm{3}}}^{\mathrm{\text{'}}}\}$ will be positive edges. If ${x_{\mathrm{2}}}^{\mathrm{\text{'}}}\notin$$\Phi$, then $\{{x_{\mathrm{1}}}^{\mathrm{\text{'}}},{x_{\mathrm{2}}}^{\mathrm{\text{'}}}\}$ and $\{{x_{\mathrm{2}}}^{\mathrm{\text{'}}},{x_{\mathrm{3}}}^{\mathrm{\text{'}}}\}$ will be negative, which implies that the number of negative edges is even in $C^{″}$. Thus $C^{″}$ is positive and ${\Sigma }_{\mathrm{1}}$ is balanced.

Case 2 Assume $p_{\mathrm{1}}\ge \mathrm{3}$ and $\exists p_i=\mathrm{2}$ for $i\in \{\mathrm{2},$$\mathrm{3},\cdots ,k\}$. Now $\Sigma$ is connected. Let $V(\Sigma )=V_{\mathrm{1}}\bigcup V_{\mathrm{2}}$, where

$V_{\mathrm{1}}=\{(u,v):u=\mathrm{0}\mathrm{a}\mathrm{n}\mathrm{d}v\mathrm{i}\mathrm{s}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}\}\bigcup \{(u,v):u\in \{\mathrm{1,2},\cdots ,p_{\mathrm{1}}-\mathrm{1}\}\mathrm{a}\mathrm{n}\mathrm{d}v\mathrm{i}\mathrm{s}\mathrm{n}\mathrm{o}\mathrm{t}\mathrm{o}\mathrm{d}\mathrm{d}-\mathrm{m}\mathrm{u}\mathrm{l}\mathrm{t}\mathrm{i}\mathrm{p}\mathrm{l}\mathrm{e}\mathrm{o}\mathrm{f}\mathrm{p}\mathrm{r}\mathrm{i}\mathrm{m}\mathrm{e}\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{s}\};$

$V_{\mathrm{2}}=\{(u,v):u=\mathrm{0}\mathrm{a}\mathrm{n}\mathrm{d}v\mathrm{i}\mathrm{s}\mathrm{o}\mathrm{d}\mathrm{d}\}\bigcup \{(u,v):u\in \{\mathrm{1,2},\cdots ,p_{\mathrm{1}}-\mathrm{1}\}\mathrm{a}\mathrm{n}\mathrm{d}v\mathrm{i}\mathrm{s}\mathrm{o}\mathrm{d}\mathrm{d}-\mathrm{m}\mathrm{u}\mathrm{l}\mathrm{t}\mathrm{i}\mathrm{p}\mathrm{l}\mathrm{e}\mathrm{o}\mathrm{f}\mathrm{p}\mathrm{r}\mathrm{i}\mathrm{m}\mathrm{e}\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{s}\}.$

Suppose $C^{‴}$ is an arbitrary cycle in $\Sigma$. If all edges of $C^{‴}$ are positive, then $C^{‴}$ is positive. If $C^{‴}$ contains a negative edge $\{(u,v),(u^{\text{'}},v^{\text{'}})\}$, then this edge has one vertex in $V_{\mathrm{1}}$ and the other in $V_{\mathrm{2}}$ from the proof of Lemma 4. Without loss of generality, assume that $(u,v)\in V_{\mathrm{1}}$ and $(u^{\text{'}},v^{\text{'}})$$\in V_{\mathrm{2}}$. Next, we will prove that another negative edge which associates to $(u^{\text{'}},v^{\text{'}})$ is required. Let above edge be $\{(u^{\text{'}},v^{\text{'}}),(u^{″},v^{″})\}$. Neither of the vertices of $V_{\mathrm{2}}$ is adjacent to each other, $(u^{″},v^{″})\in V_{\mathrm{1}}$ since $\Sigma$ is connected. $V({\Sigma }_{\mathrm{2}})\bigcap \Phi =\mathrm{\varnothing }$ and $v^{\text{'}}$ is odd. $v^{″}$ is even and $(u^{″},v^{″})$ is not in $\Phi$. Therefore $\{(u^{\text{'}},v^{\text{'}}),(u^{″},v^{″})\}$ is negative, and the negative occurs in pairs. It is easy to conclude that $C^{‴}$ is positive. Thus $\Sigma$ is balanced.

Remark 1   If $G=\mathrm{C}\mathrm{a}{\mathrm{y}}^{+}(Z_{\mathrm{2}}\times Z_{\mathrm{2}},\Phi )$, then $\Sigma =$$(G,\sigma )$ does not contain cycles. However, $\Sigma$ is balanced. (In fact, $\Sigma$ is disconnected and has exactly two connected components, say ${\Sigma }_{\mathrm{1}}$ having vertex set $V({\Sigma }_{\mathrm{1}})=\{(\mathrm{0,0}),(\mathrm{1,1})\}$ and ${\Sigma }_{\mathrm{2}}$ having vertex set $V({\Sigma }_{\mathrm{2}})=\{(\mathrm{0,1}),(\mathrm{1,0})\}$. For ${\Sigma }_{\mathrm{1}}$, by definition of signature function $\sigma$, we have $\sigma (\{(\mathrm{0,0}),(\mathrm{1,1})\})=+\mathrm{1}$ since $(\mathrm{1,1})$$\in \Phi$, $(\mathrm{0,0})\notin \Phi$ and $(\mathrm{0,0})$ is adjacent to $(\mathrm{1,1})$. For ${\Sigma }_{\mathrm{2}}$, neither of $V({\Sigma }_{\mathrm{2}})$ is in $\Phi$ and $(\mathrm{0,1})$ is adjacent to $(\mathrm{1,0})$, hence $\sigma (\{(\mathrm{0,1}),(\mathrm{1,0})\})=-\mathrm{1}$. The tree has no cycle and we can know that each tree is balanced according to the proof of Lemma 3. $\Sigma$ is balanced since it is the union of two balanced trees.)

Remark 2   If $G=\mathrm{C}\mathrm{a}{\mathrm{y}}^{+}(Z_{\mathrm{2}}\times Z_{\mathrm{2}},\Phi )$, then it follows from Remark 1 that $\eta (\Sigma )$ is balanced. Also, $L(\Sigma )$ is an empty graph and $C_E(\Sigma )$ is a null graph, therefore they all can be considered as balanced (see Fig. 6). Hence in the below proof, this case will be omitted and not considered.

Fig. 6 $\mathit{\Sigma }=(\mathbf{C}\mathbf{a}{\mathbf{y}}^{+}({\mathit{Z}}_{\mathrm{2}}\times {\mathit{Z}}_{\mathrm{2}},\mathit{\Phi }),\mathit{\sigma })$ and its three derived graphs

Next, the balance of three derived graphs $\eta (\Sigma )$, $L(\Sigma )$ and $C_E(\Sigma )$ is discussed.

Lemma 5^[5] $G_n$ is bipartite if and only if either $n$$=\mathrm{3}$ or $n$ is even.

It is known that the bipartite graph contains no odd cycle. So we have

Corollary 1   The negation of balanced bipartite signed graph is always balanced.

Lemma 6^[16] For an integer $n$, if $i\in \phi (n)$, then $(n-i)\in \phi (n)$ and if $i\notin \phi (n)$ then $(n-i)\notin \phi (n)$.

Theorem 2   Let $\Sigma =(G,\sigma )$ be an addition Cayley signed graph, where $G=\mathrm{C}\mathrm{a}{\mathrm{y}}^{+}(Z_{p_{\mathrm{1}}}\times Z_{p_{\mathrm{1}}^{{\alpha }_{\mathrm{1}}}{p}_{\mathrm{2}}^{{\alpha }_{\mathrm{2}}}\cdots p_k^{{\alpha }_k}},$$\Phi )$ and all $p_{\mathrm{1}},p_{\mathrm{2}},\cdots ,p_k$ are distinct prime factors. Then $\eta (\Sigma )$ is balanced if and only if one of the following conditions holds:

(i) one of the prime factors is 2;

(ii) $G=\mathrm{C}\mathrm{a}{\mathrm{y}}^{+}(Z_{\mathrm{3}}\times Z_{\mathrm{3}},\Phi )$.

Proof  

Necessity: Contrarily, assume that $p_i\ge \mathrm{3}$ for any $i=\mathrm{1,2},\cdots ,k$ and ${\alpha }_i\ge \mathrm{1}$ except for $G=\mathrm{C}\mathrm{a}{\mathrm{y}}^{+}$$(Z_{\mathrm{3}}\times Z_{\mathrm{3}},\Phi )$. The numbers 1 and 2 are both in $\phi (p_{\mathrm{1}})$ and $\phi (p_{\mathrm{1}}^{{\alpha }_{\mathrm{1}}}{p}_{\mathrm{2}}^{{\alpha }_{\mathrm{2}}}\cdots p_k^{{\alpha }_k})$. Let $n_{\mathrm{1}}=p_{\mathrm{1}}^{{\alpha }_{\mathrm{1}}}{p}_{\mathrm{2}}^{{\alpha }_{\mathrm{2}}}\cdots p_k^{{\alpha }_k}$, then we have $n_{\mathrm{1}}-\mathrm{1}$,$n_{\mathrm{1}}-\mathrm{2}\in \phi (n_{\mathrm{1}})$ using Lemma 6. Now let us consider a cycle $C=((\mathrm{0,0}),(\mathrm{1},n_{\mathrm{1}}-\mathrm{2}),(\mathrm{1,1}),(\mathrm{0,0}))$ in $\Sigma$. It is not difficult to see that $C$ is all-positive and $\eta (C)$ is all-negative. Thus $\eta (\Sigma )$ is unbalanced. This is a contradiction.

Sufficiency:

Case 1 Suppose one of the prime factors is 2. In this case, $\Sigma$ is balanced according to Theorem 1. The order of $\Sigma$ is even and $\Sigma$ is bipartite using Lemma 5. Applying Corollary 1, $\eta (\Sigma )$ is balanced.

Case 2 Suppose $G=\mathrm{C}\mathrm{a}{\mathrm{y}}^{+}(Z_{\mathrm{3}}\times Z_{\mathrm{3}},\Phi )$. Obviously, $\eta (\Sigma )$ is balanced (see Fig. 7).

Fig. 7 $\mathit{\Sigma }=(\mathbf{C}\mathbf{a}{\mathbf{y}}^{+}({\mathit{Z}}_{\mathrm{3}}\times {\mathit{Z}}_{\mathrm{3}},\mathit{\Phi }),\mathit{\sigma })$ and its derived graph $\mathit{\eta }(\mathit{\Sigma })$

Lemma 7^[17] $\Sigma$ is balanced if and only if it switc- hes to an all-positive signature, and it is unbalanced if and only if it switches to an all-negative signature.

Lemma 8^[18] For a sigraph $\Sigma$, $L(\Sigma )$ is balanced if and only if the following conditions hold:

(i) for any cycle $Z$ in $\Sigma$,

(a) if $Z$ is all-negative, then $Z$ has even length;

(b) if $Z$ is heterogeneous, then $Z$ has an even number of negative sections with even length;

(ii) for $v\in V(\Sigma )$, if $d(v)>\mathrm{2}$, then there is at most one negative edge incident at $v$ in $\Sigma$.

Theorem 3   Let $\Sigma =(G,\sigma )$ be an addition Cayley signed graph, where $G=\mathrm{C}\mathrm{a}{\mathrm{y}}^{+}(Z_{p_{\mathrm{1}}}\times Z_{p_{\mathrm{1}}^{{\alpha }_{\mathrm{1}}}{p}_{\mathrm{2}}^{{\alpha }_{\mathrm{2}}}\cdots p_k^{{\alpha }_k}},\Phi )$ and all $p_{\mathrm{1}},p_{\mathrm{2}},\cdots ,p_k$ are distinct prime factors. Then $L(\Sigma )$ is balanced if and only if $\Sigma$ is balanced.

Proof  

Necessity: Contrarily, assume that $\Sigma$ is unbalanced. By Theorem 1, we have $p_i\ge \mathrm{3}$ for any $i=\mathrm{1,2},\cdots ,k$. In this case, we have $d(v)\ge |\Phi |-\mathrm{1}$ which is greater than 2 for all vertices. Note that $(\mathrm{0,1})$ is adjacent to vertices $(\mathrm{1,0}),(\mathrm{2,0}),\cdots ,(p_{\mathrm{1}}-\mathrm{1,0})$ respectively. None of these $p_{\mathrm{1}}$ vertices is in $\Phi$, hence $d^{-}((\mathrm{0,1}))\ge$$p_{\mathrm{1}}-\mathrm{1}$. $p_{\mathrm{1}}\ge \mathrm{3}$. It follows from Lemma 8 that $L(\Sigma )$ is unbalanced. This is a contradiction.

Sufficiency: Assume that $\Sigma$ is balanced. According to Lemma 7, $\Sigma$ can be considered all-positive. Therefore $L(\Sigma )$ is all-positive and balanced.

Lemma 9^[8] For any sigraph $\Sigma$, $C_E(\Sigma )$ is bala- nced if and only if $\Sigma$ is a balanced sigraph such that for every vertex $v\in V(\Sigma )$ with $d(v)\ge \mathrm{3}$,

(i) if $d(v)>\mathrm{3}$ then $d^{-}(v)=\mathrm{0}$;

(ii) if $d(v)=\mathrm{3}$ then $d^{-}(v)=\mathrm{0}$ or $d^{-}(v)=\mathrm{2}$; and