On Some Properties of Addition Signed Cayley Graph ${\mathsf{\Sigma }}_{\mathit{n}}^{\mathbf{\wedge }}$

Abstract

We define an addition signed Cayley graph on a unitary addition Cayley graph $G_n$ represented by ${\mathsf{\Sigma }}_n^{\wedge }$, and study several properties such as balancing, clusterability and sign compatibility of the addition signed Cayley graph ${\mathsf{\Sigma }}_n^{\wedge }$. We also study the characterization of canonical consistency of ${\mathsf{\Sigma }}_n^{\wedge }$, for some n.

1. Introduction

We refer to standard books of Harary [1] and West [2] for graph theory. For the signed graphs, we refer to Zaslavsky [3,4]. All the signed graphs considered in this paper are simple, finite and loopless.

For the preliminaries, definition and notation of signed graph S, underlying graph $S^u$, its negation $\eta \left(S\right)$, signed isomorphism and its positive (negative) section, we refer to [5,6].

Some Basic Lemma and Theorems which are used in this paper are stated below as a reference.

Lemma 1

([7]). A signed graph in which every chordless cycle is positive is balanced.

Theorem 1

([8]). A signed graph S is clusterable if—and only if—S does not contains a cycle with exactly one negatively charged edge.

For balancing, clusterability, marking, canonical marking ($\mathcal{C}$-marking), consistency, $\mathcal{C}$-consistency, S consistency, sign compatibility, line signed graph $L\left(S\right)$, line signed root graph, ×-line signed graph, ×-line signed root graph and the common-edge signed graph $C_E\left(S\right)$ of signed graph, S we refer to [6,9,10,11,12,13,14,15,16].

Addition Signed Cayley Graph ${\mathsf{\Sigma }}_n^{\wedge }$

A unitary addition Cayley graph $G_n$, where $n\in I^{+}$, $I^{+}$ is set of positive integers, is a graph in which the vertex set is a ring of integers modulo n, $Z_n$. Any two vertices $x_1$ and $x_2$ are adjacent in $G_n$ if—and only if—$(x_1+x_2)\in U_n$, where $U_n$ denotes the unit set.

Unitary addition Cayley graphs for n = 2, 3, 4, 5, 6 and 7 are shown in Figure 1.

The study of unitary Cayley graphs began in order to gain some insight into the graph representation problem (see [17]), and we can extend it to the signed graphs (see [18]).

Now, we introduce the definition of an addition signed Cayley graph ${\mathsf{\Sigma }}_n^{\wedge }$ as follows:

The addition signed Cayley graph ${\mathsf{\Sigma }}_n^{\wedge }=(G_n,{\sigma }^{\wedge })$ is a signed graph whose underlying graph is a unitary addition Cayley graph $G_n$, where $n\in I^{+}$ and for an edge $ab$ of ${\mathsf{\Sigma }}_n^{\wedge }$,

$${\sigma }^{\wedge }\left(ab\right)=\left\{\begin{array}{cc}+\hfill & \mathrm{if}a,b\in U_n,\hfill \\ -\hfill & \mathrm{otherwise}.\hfill \end{array}\right.$$

Examples of addition signed Cayley graph for n = 5, 6 and 10 can be seen in Figure 2a–c. Throughout the paper, we consider $n\ge 2$.

2. Some Properties of ${\mathsf{\Sigma }}_{\mathit{n}}^{\wedge }$

2.1. Balancing in ${\mathsf{\Sigma }}_n^{\wedge }$

The balancing of some derived signed Cayley graphs has been studied in the literature (see [19]). Here, we find out the property of balancing for the addition signed Cayley graph ${\mathsf{\Sigma }}_n^{\wedge }$, for which the following well-known result can be used as a tool.

Theorem 2

([20]). $G_n$, $n\ge 2,$ is bipartite if—and only if—either $n=3$ or n is even.

Lemma 2.

$i\in U_n\Rightarrow (n-i)\in U_n$ and $i\notin U_n\Rightarrow (n-i)\notin U_n$.

Lemma 3.

Addition signed Cayley graph ${\mathsf{\Sigma }}_n^{\wedge }=(G_n,{\sigma }^{\wedge })$, for n even, is an all-negative signed graph.

Proof. 

Given an addition signed Cayley graph ${\mathsf{\Sigma }}_n^{\wedge }=(G_n,{\sigma }^{\wedge })$, where n is even. Suppose the conclusion is false. Let there be a positive edge, say $ij$, in ${\mathsf{\Sigma }}_n^{\wedge }$. By the definition of ${\mathsf{\Sigma }}_n^{\wedge }$, $i,j\in U_n$. Since n is even, $U_n$ consists only of odd numbers. Thus, i and j are odd numbers and their addition $i+j$ is an even number. This shows that $i+j\notin U_n$, i.e., i and j, are not adjacent in ${\mathsf{\Sigma }}_n^{\wedge }$. Thus, we have a contradiction. Hence, if n is even, then ${\mathsf{\Sigma }}_n^{\wedge }$ is all-negative signed graph. □

Sampathkumar [21] gave the famous characterization to prove the balancing in a signed graph, which is as follows:

Theorem 3

(Marking Criterion [21]). A signed graph $S=(G,\sigma )$ is balanced if—and only if—there exists a marking μ of its vertices such that each edge $uv$ in S satisfies $\sigma \left(uv\right)=\mu \left(u\right)\mu \left(v\right)$.

Lemma 4.

For the addition signed Cayley graph ${\mathsf{\Sigma }}_n^{\wedge }=(G_n,{\sigma }^{\wedge })$, ${\mathsf{\Sigma }}_n^{\wedge }$ is a balanced signed graph, if for any prime p, $n=p^a$.

Proof. 

$n=p^a$, where p is a prime number. Now, we assign a marking $\mu$ to the vertices of ${\mathsf{\Sigma }}_n^{\wedge }$ in such a manner that if $u\in U_n$, then $\mu \left(u\right)=+$ and if $u\notin U_n$, then $\mu \left(u\right)=-$, ∀$u\in V\left({\mathsf{\Sigma }}_n^{\wedge }\right).$ Suppose there is an edge, say $ij$, in ${\mathsf{\Sigma }}_n^{\wedge }$.

Case I: Let ${\sigma }^{\wedge }\left(ij\right)=+.$ Then, $i,j\in U_n$ and according to the marking $\mu \left(i\right)=\mu \left(j\right)=+.$ Thus, ${\sigma }^{\wedge }\left(ij\right)=\mu \left(i\right)\mu \left(j\right)=+.$

Case II: Let ${\sigma }^{\wedge }\left(ij\right)=-.$ Then, there are three possibilities:

$\left(a\right)$

$i\in U_n$, $j\notin U_n$.

$\left(b\right)$

$i\notin U_n$, $j\in U_n$.

$\left(c\right)$

$i,j\notin U_n$.

Now, for (a) and (b), by marking $\mu$, we get $\mu \left(j\right)=-$ and $\mu \left(i\right)=+$ or vice versa. Therefore, ${\sigma }^{\wedge }\left(ij\right)=\mu \left(i\right)\mu \left(j\right)=-.$ Now, if $i,j\notin U_n$. Then, i and j are both multiples of p, and then $i+j=kp$, where k is some positive integer and $i+j\notin U_n$. So $ij\notin E\left({\mathsf{\Sigma }}_n^{\wedge }\right)$. Thus, condition (c) is not possible. So in every condition we get ${\sigma }^{\wedge }\left(ij\right)=\mu \left(i\right)\mu \left(j\right)$. Since $ij$ is an arbitrary edge, using Theorem 3, ${\mathsf{\Sigma }}_n^{\wedge }$ is balanced. □

Theorem 4.

The addition signed Cayley graph ${\mathsf{\Sigma }}_n^{\wedge }$ is balanced if—and only if—either n is even or if n has exactly one prime factor, then n is odd.

Proof. 

Necessity: First, suppose ${\sum }_n^{\wedge }$ is balanced. Now, let $n=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\dots p_m^{{\alpha }_m}$; $p_1,p_2,\dots ,p_m$ being distinct primes, $p_1\ne 2$, $p_1\le p_2\le \dots \le p_m$.

In the unitary addition Cayley graph $G_n$, $p_1+1\ne k_1{p}_i$ for $i=1,2,\cdots ,m$ and $k_1$ are some positive integers i.e., $p_1+1\in U_n$, so $p_1$ is adjacent with one. Now, we claim that $p_1$ and $p_2$ are adjacent in $G_n$. On the contrary, suppose $p_1{p}_2$ is not an edge in $G_n$. Then, $p_1+p_2\notin U_n$. Thus, $p_1+p_2=k_2{p}_i$ for some $i=1,2,\cdots ,m$ and $k_2$ are some positive integers. Let $p_1+p_2$ be a multiple of $p_1$.

$$\begin{array}{cc}\hfill p_1+p_2& =\alpha p_1\hfill \\ \hfill p_2& =\alpha p_1-p_1\hfill \\ \hfill & =(\alpha -1)p_1\hfill \end{array}$$

for the positive integer $\alpha$, a contradiction. With the same argument, we can show that $p_1+p_2$ is not a multiple of $p_2$. Now, let $p_1+p_2=\alpha p_i$, for $i=3,4,\cdots ,m.$ As we know, the addition of two prime factors is always even; $p_1+p_2$ is even. So, $\alpha$ is even and is at least 2. However, as $p_1<p_2<p_i$, $p_1+p_2$ is always less than any multiple of $p_i$ for $i=3,4,\cdots ,m.$ Thus, $p_1+p_2\in U_n$ and $p_1{p}_2$ is an edge in $G_n$. Next, if $p_2$ is adjacent to 1 in $G_n$, we get a cycle

$$C=(p_1,p_2,1,p_1)$$

in ${\mathsf{\Sigma }}_n^{\wedge }$. Clearly, $p_1$ and $p_2$ are not in $U_n$, then by definition of ${\mathsf{\Sigma }}_n^{\wedge }$, C is a negative cycle. Thus, we have a negative cycle in ${\mathsf{\Sigma }}_n^{\wedge }$, implying that ${\mathsf{\Sigma }}_n^{\wedge }$ is not balanced. Now, suppose $p_2+1\notin E\left(G_n\right)$, since $p_2+1\notin U_n.$ Then, $p_2+1=c{p}_i$; $i=1,2,\cdots ,m$, c are positive integers. Clearly,

$$p_2+1=\alpha p_1$$

(1)

$\alpha$ is a positive integer.

Since $p_2\notin U_n$, according to Lemma 2, $n-p_2\notin U_n$. Next, we claim that $n-p_2$ is adjacent to 1 or $n-p_2+1=n-(p_2-1)\in U_n$. If $p_2-1\in U_n,$ then according to Lemma 2, $n-p_2+1=n-(p_2-1)\in U_n.$ Suppose $p_2-1\notin U_n.$ Then, $p_2-1=\beta p_i$; $i=1,2,\cdots ,m$, $\beta$ are positive integers. Let $p_2-1=\beta p_1.$ However, from Equation (1), $p_2=\alpha p_1-1.$ This implies

$$\begin{array}{cc}\hfill p_2-1& =\beta p_1\hfill \\ \hfill \alpha p_1-1-1& =\beta p_1\hfill \\ \hfill \alpha p_1-2& =\beta p_1\hfill \\ \hfill \alpha p_1-\beta p_1& =2\hfill \\ \hfill (\alpha -\beta )p_1& =2.\hfill \end{array}$$

This is not possible, as $p_1$ is at least $3.$ Thus, $p_2-1$ is not a multiple of any of the $p_i$s, whence $p_2-1\in U_n$. Hence, $n-p_2+1=n-(p_2-1)\in U_n,$ whence $n-p_2$ is adjacent to 1 in $G_n$. Now, $n-p_2+p_1=n-(p_2-p_1).$ Since $p_1<p_2<\cdots p_m$, $p_2-p_1\ne k{p}_i$; $i=2,3,\cdots m.$, k is a positive integer. Additionally, $p_2-p_1$ is not a multiple of $p_1.$ This shows that $p_2-p_1\in U_n$ and by Lemma 2, $n-(p_2-p_1)\in U_n.$ This shows that $n-p_2$ is adjacent to $p_1$ in ${\mathsf{\Sigma }}_n.$ Thus, we get a cycle

$$C^{\prime }=(p_1,n-p_2,1,p_1)$$

in ${\mathsf{\Sigma }}_n.$ Clearly, $p_1$ and $n-p_2$ do not belong to $U_n$ and $1\in U_n.$ Then, by definition ${\mathsf{\Sigma }}_n^{\wedge }$, we have a cycle $C^{\prime }$ with three negative edges. Thus, a contradiction. So, by contraposition, necessity is true.

Sufficiency: Let n be even. Then, according to Lemma 3, ${\mathsf{\Sigma }}_n^{\wedge }$ is an all-negative signed graph. Additionally, according to Theorem 2, $G_n$ is a bipartite graph. Hence, ${\mathsf{\Sigma }}_n^{\wedge }$, by Lemma 3 and Theorem 2, is balanced.

Now, let n be odd, with exactly one prime factor. Then, according to Lemma 4, ${\mathsf{\Sigma }}_n^{\wedge }$ is balanced, hence the theorem. □

2.2. Clusterability in ${\mathsf{\Sigma }}_n^{\wedge }$

Theorem 5.

The addition signed Cayley graph ${\mathsf{\Sigma }}_n^{\wedge }=(G_n,{\sigma }^{\wedge })$ is clusterable.

Proof. 

Given an addition signed Cayley graph ${\mathsf{\Sigma }}_n^{\wedge }=(G_n,{\sigma }^{\wedge })$. Suppose $v\in V\left({\mathsf{\Sigma }}_n^{\wedge }\right)$. Define $V^{*}\subseteq V\left({\mathsf{\Sigma }}_n^{\wedge }\right)$, such that $V^{*}=\left\{u_i:u_i\in V\left({\mathsf{\Sigma }}_n^{\wedge }\right)\mathrm{and}{\sigma }^{\wedge }\left(v{u}_i\right)=+\right\}$. By the definition of ${\mathsf{\Sigma }}_n^{\wedge }$, clearly $u_i$ and v are in $U_n$.

If, for i and j, ($i\ne j$), $u_i$ and $u_j$ are adjacent, then ${\sigma }^{\wedge }\left(u_i{u}_j\right)=+$. Thus, $U_n\subseteq V^{*}$. Since $\left|U_n\right|=\varphi \left(n\right)$, $n-\varphi \left(n\right)=k$ (say) vertices are not in $U_n$. Thus, only negative edges are incident on these k vertices. Put all these vertices in the k partition $V_1,V_2,\cdots ,V_k$, such that each partition contains exactly only one vertex. The clearly induced subgraph $<V^{*}>$ is all positive. Additionally, no positive edge joins the vertex of $V^{*}$ with the vertex of any of $V_i$, for $i=1,2,\cdots ,k$, and there is no edge $xy$, such that ${\sigma }^{\wedge }\left(xy\right)=-$ and $x,y\in V^{*}$. Thus, there exists a partition of the $V\left({\mathsf{\Sigma }}_n^{\wedge }\right)$, such that every positive edge has end vertices within the same subset and every negative edge has end vertices in a different subset. Hence, the proof. □

2.3. Sign-Compatibility in ${\mathsf{\Sigma }}_n^{\wedge }$

Theorem 6

([22]). A signed graph S is sign compatible if—and only if—S does not contain a sub signed graph isomorphic to either of the two signed graphs. $S_1$ formed by taking the path $P_4=(x,u,v,y)$ with both edges $xu$ and $vy$ negative and edge $uv$ positive, and $S_2$ formed by taking $S_1$ and identifying the vertices x and y (Figure 3).

Theorem 7.

Addition signed Cayley graph ${\mathsf{\Sigma }}_n^{\wedge }$ is sign compatible if—and only if—n is 3 or even.

Proof. 

Let addition signed Cayley graph ${\mathsf{\Sigma }}_n^{\wedge }$ be sign compatible. If possible, suppose the conclusion is not true. Let n be odd but not 3. Now, $01\in E\left({\mathsf{\Sigma }}_n^{\wedge }\right)$. As, $n-2+1=n-1\in U_n$, $1(n-2)\in E\left({\mathsf{\Sigma }}_n^{\wedge }\right)$. Additionally, $n-2+0=n-2\in U_n$. Thus, we have a triangle $(0,1,n-2,0)$ with one positive edge $1(n-2)$ and two negative edges 01 and $(n-2)0$, which again contradict Theorem 6. Hence, the condition is necessary.

Next, let n be even. Thus, according to Lemma 3, ${\mathsf{\Sigma }}_n^{\wedge }$, which is all-negative, is trivially sign compatible. If $n=3$, then ${\mathsf{\Sigma }}_n^{\wedge }$ is $P_3$, which is trivially sign compatible. □

Acharya and Sinha [23] showed that every line signed graph is sign compatible. Next, we discuss the value of n for which ${\mathsf{\Sigma }}_n^{\wedge }$ is a line signed graph.

Theorem 8.

$G_n$ is a line graph if—and only if—n is equal to 2 or 3 or 4 or 6.

Proof. 

Necessity: Let $G_n$ be a line graph. Meanwhile, n is not equal to 2, 3, 4 and 6.

Case I: n is prime. It is clear that $n\ge 5.$ Here, n is prime, so by the definition of $U_n$, there are numbers from 1 to $(n-1)$ in $U_n.$ 0 is connected to every vertex of $G_n.$ The other vertex, $i\ne 0$, in $G_n$ is not connected to only $(n-i)$ by definition. For any $i,j\in V\left(G_n\right)$; $i\ne 0$, $j\ne 0$ there is an induced subgraph in $G_n$ (see Figure 4).

Thus, $G_n$ contains forbidden subgraph for a line graph. Thus, $G_n$ is not a line graph.

Case II: n is not prime. 1 is connected to 0 in $G_n.$ Next, 1 is connected to $p_1,$ as $p_1+1\in U_n,$ where $p_1$ is the smallest factor of $n.$ Let $\alpha p_1=n$, for a positive integer $\alpha$. Now,

$$\begin{array}{cc}\hfill 1+(\alpha -1)p_1& =1+\alpha p_1-p_1\hfill \\ \hfill & =1+n-p_1\hfill \\ \hfill & =n-(p_1-1).\hfill \end{array}$$

Since $p_1-1\in U_n,$ by Lemma 2, $n-(p_1-1)\in U_n.$ Thus, 1 and $(a-1)p_1$ are adjacent in $G_n.$ Additionally, 0 is not adjacent to $p_1$ and $(a-1)p_1$, because their sum is a multiple of $p_1.$ In the same way, $p_1$ and $(a-1)p_1$ are not connected in $G_n$ because their sum is a multiple of $p_1.$ So, we have an induced subgraph in $G_n$ (see Figure 5). Thus, there is a forbidden subgraph $K_{1,3}$ of a line graph. Additionally, $G_n$ is not a line graph.

Sufficiency: Let $n=2$ or $n=3$ or $n=4$ or $n=6$. Then, $G_2\cong L\left(P_3\right)$, $G_3\cong L\left(P_4\right)$, $G_4\cong L\left(C_4\right)$ and $G_6\cong L\left(C_6\right)$ (see Figure 6). Hence, the result. □

Theorem 9.

${\mathsf{\Sigma }}_n^{\wedge }$ is a line signed graph if—and only if—$n=2$ or $n=3$ or $n=4$ or $n=6$.

Proof. 

Necessity: Let, if possible, n be unequal to 2, 3, 4 and 6. Theorem 8 shows that $G_n\neg \cong L\left(G\right)$, for any graph G. Thus, a contradiction and the condition are necessary.

Sufficiency: Now, suppose $n=2$ or $n=3$ or $n=4$ or $n=6$. Line signed graphs of an addition signed Cayley graph, for these values of n, are displayed in Figure 7, hence the sufficiency. □

Remark 1.

${\mathsf{\Sigma }}_n^{\wedge }$ is a ×-line signed graph if—and only if—$n=2$ or $n=3$ or $n=4$ or $n=6$.

Proof. 

Let ${\mathsf{\Sigma }}_n^{\wedge }$ be a $\times -$line signed graph. We know that the underlying structure for line signed graphs and $\times -$line signed graphs is the same. Thus, the condition comes from Theorem 8.

Next, let $n\in \{2,3,4,6\}$. ${\mathsf{\Sigma }}_2^{\wedge }$, ${\mathsf{\Sigma }}_3^{\wedge }$, ${\mathsf{\Sigma }}_4^{\wedge }$ and ${\mathsf{\Sigma }}_6^{\wedge }$ and its $\times -$line signed root graphs are displayed in Figure 8. From Theorem 4, it is clear that for these values of $n,$ an addition signed Cayley graph is balanced. Additionally, $L_{\times }\left(S\right)$ of any signed graph is always balanced, and its underlying graph is a line graph (see [24]). This result comes from Theorems 4 and 8. □

2.4. $\mathcal{C}$-Consistency of ${\mathsf{\Sigma }}_n^{\wedge }$

Lemma 5.

For any prime p, $p\ne 2$ and $n=p^{\alpha }$, the $d^{-}\left(2\right)$ and $d^{-}\left(4\right)$ in ${\mathsf{\Sigma }}_n^{\wedge }$ is odd.

Proof. 

Given a ${\mathsf{\Sigma }}_n^{\wedge }=(G_n,{\sigma }^{\wedge })$, where $n=p^{\alpha }$ and p is an odd prime. Since n is odd; 2, $4\in U_n$. It is obvious that $d^{-}\left(2\right)$ and $d^{-}\left(4\right)$ in ${\mathsf{\Sigma }}_n^{\wedge }$ appear only when 2 and 4 are adjacent to $kp$, where k is some positive integer. Now, $(2+4)+cp\ne kp$; positive integers c and k. Additionally, 2 and 4 are connected to all the multiples of p, which are $p^{\alpha -1}$. Therefore $d^{-}\left(2\right)$$\left(d^{-}\left(4\right)\right)=p^{\alpha -1}$ is odd, hence the lemma. □

Theorem 10

([25]). Let a, b and m be integers with m positive. The linear congruence $ax\equiv b(modm)$ is soluble if and only if $(a,m)|b$. If $x_0$ is a solution, there are exactly $(a,m)$ incongruent solutions given by $\{x_0+tm/(a,m)\}$, where $t=0,1,\dots ,(a,m)-1$.

Corollary 1.

If $(a,m)=1$ then the congruence $ax\equiv b(modm)$ has exactly one incongruent solution.

Lemma 6.

In addition, signed Cayley graph ${\mathsf{\Sigma }}_n^{\wedge }=(G_n,{\sigma }^{\wedge })$, if $n=p_1^{a_1}{p}_2^{a_2}$, where $p_1$ and $p_2$ are two distinct odd primes, then $d^{-}\left(2\right)\left(d^{-}\left(4\right)\right)$ = odd.

Proof. 

Given that $n=p_1^{a_1}{p}_2^{a_2}$ in ${\mathsf{\Sigma }}_n^{\wedge }$, $p_1$ and $p_2$ are distinct odd primes. As n is odd, $2\in U_n$. Now, the negative degree of 2 of ${\mathsf{\Sigma }}_n^{\wedge }$ appears only when 2 is adjacent with the multiples of $p_1$ and $p_2$. Let $A_i=\left\{c{p}_i;\mathrm{c}\mathrm{certain}\mathrm{positive}\mathrm{integers},i=1,2\right\}$. Then,

$$\begin{array}{c}\hfill \left|A_1\right|=p_1^{a_1-1}{p}_2^{a_2}\\ \hfill \left|A_2\right|=p_1^{a_1}{p}_2^{a_2-1}\end{array}$$

and

$$\begin{array}{c}\hfill \left|A_1\cap A_2\right|=p_1^{a_1-1}{p}_2^{a_2-1}\end{array}$$

Thus, using the inclusion–exclusion principle

$$\begin{array}{c}\hfill \left|A_1\cup A_2\right|=p_1^{a_1-1}{p}_2^{a_2}+p_1^{a_1}{p}_2^{a_2-1}-p_1^{a_1-1}{p}_2^{a_2-1}\end{array}$$

Since $c{p}_1\left(p_2\right)+2=p_2\left(p_1\right)$, for certain positive integers c and so, $c{p}_1\left(p_2\right)2\notin E\left({\mathsf{\Sigma }}_n^{\wedge }\right)$ for those c. Thus, according to Theorem 10, we have

$$\begin{array}{c}\hfill p_{1}x\equiv -2\left(\mathrm{mod}{p}_2\right)\end{array}$$

(2)

and

$$\begin{array}{c}\hfill p_{2}y\equiv -2\left(\mathrm{mod}{p}_1\right)\end{array}$$

(3)

Due to Corollary 1, we have an incongruent solution $x_0$ (say), which is unique for Equation (2). So, for Equation (2) where $p_{1}x+2<n$, we have:

$$\begin{array}{c}\hfill x_0+0\left(p_2\right),x_0+1\left(p_2\right),x_0+2\left(p_2\right),\cdots ,x_0+(p_1^{a_1-1}{p}_2^{a_2-1}-1)\left(p_2\right)\end{array}$$

(4)

Thus, Equation (2) has $p_1^{a_1-1}{p}_2^{a_2-1}$ total solutions. Similarly, the total solutions of Equation (3) are $p_1^{a_1-1}{p}_2^{a_2-1}$. Hence,

$$\begin{array}{cc}\hfill d^{-}\left(2\right)& =p_1^{a_1-1}{p}_2^{a_2}+p_1^{a_1}{p}_2^{a_2-1}-p_1^{a_1-1}{p}_2^{a_2-1}-p_1^{a_1-1}{p}_2^{a_2-1}-p_1^{a_1-1}{p}_2^{a_2-1}\hfill \\ \hfill & =p_1^{a_1-1}{p}_2^{a_2-1}(p_1+p_2-3)\hfill \end{array}$$

$p_1$ and $p_2$ are odd primes, which implies $d^{-}\left(2\right)$ is odd. The proof for $d^{-}\left(4\right)$ is analogous. □

Lemma 7.

In ${\mathsf{\Sigma }}_n^{\wedge }=(G_n,{\sigma }^{\wedge })$, if $n=3^{a_1}{5}^{a_2}$, then $d^{-}\left(7\right)$ = odd.

Proof. 

This is easy to prove using the same logic as mentioned in Lemma 6. □

Theorem 11.

Let n have at most two distinct odd prime factors, then ${\mathsf{\Sigma }}_n^{\wedge }$ is $\mathcal{C}$ consistent if—and only if—n is even or 3.

Proof. 

Necessity: Let n have, at most, two distinct prime factors and let ${\mathsf{\Sigma }}_n^{\wedge }$ be $\mathcal{C}$ consistent. If possible, let n be odd but not 3.

Case (a): Let $n\equiv 1(mod3)$ or $n\equiv 2(mod3)$. As n is odd, $2\in U_n$. Clearly, 0 is adjacent with 1, 2, $n-1$ in ${\mathsf{\Sigma }}_n^{\wedge }.$ Since, $n-1+2=1\in U_n$, $n-1$ and 2 are connected in ${\mathsf{\Sigma }}_n^{\wedge }.$ Since, 3 is not a factor of n, $3\in U_n.$ Now, $2+1=3\in U_n$. Hence, 2 and 1 are adjacent in ${\mathsf{\Sigma }}_n^{\wedge }.$ Now, the cycles $Z_1=(0,1,2,0)$, $Z_2=(0,2,n-1,0)$ have a common chord with end vertices 0 and 2. By Lemma 6,

$${\mu }_{\sigma }\left(2\right)=-$$

Since the vertex $0\notin U_n$, $d\left(0\right)=d^{-}\left(0\right)=\varphi \left(n\right)=$ even. It follows,

$${\mu }_{\sigma }\left(0\right)=+.$$

Now, if either $Z_1$ or $Z_2$ is not a $\mathcal{C}$-consistent cycle, a contradiction. Thus, $Z_1$ and $Z_2$ both cycle are $\mathcal{C}$-consistent. The common chord with end vertices zero and two are oppositely marked, in contradiction with (Theorem 2, [26]).

Case (b): Let $n\equiv 0(mod3).$ Then, either $n=3^{a_1}$ or $n=3^{a_1}\times p_2^{a_2}.$ First, suppose $p_2\ne 5.$ Since, n is odd, $2,4\in U_n.$ According to Lemma 2, $n-2\in U_n.$ Clearly, 0 is adjacent to 1, 4 and $n-2$ in ${\mathsf{\Sigma }}_n^{\wedge }.$ Since, $n-2+4=n+2=2\in U_n$, $n-2$ is adjacent to 4 in ${\mathsf{\Sigma }}_n^{\wedge }.$ Now, for cycle $Z_1=(0,1,4,0)$, $Z_2=(0,4,n-2,0)$; $Z_1$, $Z_2$ have a common chord with end vertices 0 and 4. According to Lemma 6,

$${\mu }_{\sigma }\left(4\right)=-$$

Since the vertex $0\notin U_n,$$d\left(0\right)=d^{-}\left(0\right)=\varphi \left(n\right)=$ even. It follows,

$${\mu }_{\sigma }\left(0\right)=+.$$

Now, if either $Z_1$ or $Z_2$ is a cycle which is not $\mathcal{C}$ consistent, a contradiction. Therefore, $Z_1$ and $Z_2$ are the cycles which are $\mathcal{C}$-consistent. However, there is a chord whose end vertices 0 and 4 have opposite marking. Here again, we find a contradiction to the (Theorem 2, [26]).

Now, suppose $p_2=5.$ In this case, we consider two cycles $Z_1=(0,1,7,0)$ and $Z_2=(0,7,10,13,0)$ in ${\mathsf{\Sigma }}_n^{\wedge }.$ For cycles $Z_1$, $Z_2$ have a common chord with end vertices 0 and 7, according to Lemma 7,

$${\mu }_{\sigma }\left(7\right)=-$$

Since the vertex $0\notin U_n,$$d\left(0\right)=d^{-}\left(0\right)=\varphi \left(n\right)=$ even. It follows that

$${\mu }_{\sigma }\left(0\right)=+.$$

Now, if either $Z_1$ or $Z_2$ is a cycle which is not $\mathcal{C}$ consistent, this is a contradiction. Therefore, $Z_1$ and $Z_2$ are the cycles which are $\mathcal{C}$ consistent. However, the end vertices 0 and 7 have the opposite marking. Here, we have a contradiction to the (Theorem 2, [26]). Hence, n is either even or $n=3$.

Sufficiency: Let n be even. According to Lemma 3, ${\mathsf{\Sigma }}_n^{\wedge }$ is all negative. Additionally, according to Theorem 13, $d\left(v\right)=d^{-}\left(v\right)$ = even ∀$v\in V\left({\mathsf{\Sigma }}_n^{\wedge }\right).$ So, according to canonical marking ${\mu }_{\sigma }\left(v\right)=+$∀$v\in V\left({\mathsf{\Sigma }}_n^{\wedge }\right).$ So when n is even, ${\mathsf{\Sigma }}_n^{\wedge }$ is trivially $\mathcal{C}$ consistent. If $n=3$, then $G_3$ is a path, which is trivially $\mathcal{C}$- consistent, hence the result. □

3. Balance in Certain Derived Signed Graphs of ${\mathsf{\Sigma }}_{\mathit{n}}^{\wedge }$

Theorem 12.

$\eta \left({\mathsf{\Sigma }}_n^{\wedge }\right)$ is balanced if—and only if—n is 3 or even.

Proof. 

Let $\eta \left({\mathsf{\Sigma }}_n^{\wedge }\right)$ be balanced. If possible, n is odd but not 3, and p is the smallest prime factor of $n$. Since $n-2+1=n-1\in U_n$, $n-2$ and 1 are connected in ${\mathsf{\Sigma }}_n^{\wedge }$. $p+1\in U_n$ implies that p and 1 are connected in ${\mathsf{\Sigma }}_n^{\wedge }.$ Additionally, as n is odd, $2\in U_n$ and $n-2\in U_n.$ according to Lemma 2. Since, $n-2+p=n+(p-2)=p-2\in U_n$, $(n-2)p\in E\left({\mathsf{\Sigma }}_n^{\wedge }\right).$ Now, for the cycle $Z=(1,p,n-2,1)$ in ${\mathsf{\Sigma }}_n^{\wedge }$ we have a one positive edge $1(n-2)$ and two negative edges $1p$ and $p(n-2)$ in $Z.$ However, in $\eta \left({\mathsf{\Sigma }}_n^{\wedge }\right)$, there is a cycle $Z^{\prime }=(1,p,n-2,1)$ with one negative edge $1(n-2)$ and two positive edges $1p$ and $p(n-2).$ Thus, we have a negative cycle that contradicts the given condition. Therefore, the only possibility is that n is 3 or even.

Conversely, let n be even. ${\mathsf{\Sigma }}_n^{\wedge }$, according to Lemma 3 is an all-negative signed graph. So $\eta \left({\mathsf{\Sigma }}_n^{\wedge }\right)$ is balanced and is all positive. $\eta \left({\mathsf{\Sigma }}_n^{\wedge }\right)$ for $n=3$ is a tree which is trivially balanced, hence the converse. □

We present the following theorem for the degree of the vertices of $G_n$ (see [20]).

Theorem 13

([20]). Let m be any vertex of the unitary addition Cayley graph $G_n$. Then,

$$d\left(m\right)=\left\{\begin{array}{cc}\varphi \left(n\right)\hfill & \mathit{if}n\mathit{is}\mathit{even},\hfill \\ \varphi \left(n\right)\hfill & \mathit{if}n\mathit{is}\mathit{odd}\mathit{and}(m,n)\ne 1,\hfill \\ \varphi \left(n\right)-1\hfill & \mathit{if}n\mathit{is}\mathit{odd}\mathit{and}(m,n)=1.\hfill \end{array}\right.$$

Additionally, for a signed graph S, the balance property of $L\left(S\right)$ is discussed in ([27], Theorem 4).

Theorem 14.

For an additional signed Cayley graph ${\mathsf{\Sigma }}_n^{\wedge }=(G_n,{\sigma }^{\wedge })$, its line signed graph $L\left({\mathsf{\Sigma }}_n^{\wedge }\right)$ is balanced if—and only if—$n\in \left\{2,3,4,6\right\}.$

Proof. 

Let $L\left({\mathsf{\Sigma }}_n^{\wedge }\right)$ be balanced and $n\ne 2,3,4$ and 6. Now, according to Theorem 13, $d\left(0\right)=d^{-}\left(0\right)=\varphi \left(n\right)$ = even, which implies $d\left(0\right)=d^{-}\left(0\right)=\varphi \left(n\right)\ge 4.$ This shows that condition $ii$ (of Theorem 4, [27]) is not satisfied for ${\mathsf{\Sigma }}_n^{\wedge }.$ This is a contradiction. Hence, $n\in \left\{2,3,4,6\right\}.$ The converse part is easy to prove. □

For a signed graph S, the balance property of $C_E\left(S\right)$ is discussed in ([9], Theorem 13).

Theorem 15.

For an additional signed Cayley graph ${\mathsf{\Sigma }}_n^{\wedge }=(G_n,{\sigma }^{\wedge })$, its common-edge signed graph $C_E\left({\mathsf{\Sigma }}_n^{\wedge }\right)$ is balanced if—and only if—$n\in \left\{3,4,6\right\}.$

Proof. 

Let $n\notin \left\{3,4,6\right\}.$ It is clear that $0\notin U_n.$ Now, by Theorem 13, $d\left(0\right)=d^{-}\left(0\right)=\varphi \left(n\right)$ = even, which implies $d\left(0\right)=d^{-}\left(0\right)=\varphi \left(n\right)\ge 4.$ This shows that condition $ii$ (of Theorem 13, [9]) is not satisfied for ${\mathsf{\Sigma }}_n^{\wedge }.$ Thus, $C_E\left({\mathsf{\Sigma }}_n^{\wedge }\right)$ is not balanced, which is a contradiction. Hence, $n\in \left\{3,4,6\right\}$. The converse part is easy to prove. □