Open Access
Issue
Wuhan Univ. J. Nat. Sci.
Volume 27, Number 4, August 2022
Page(s) 296 - 302
DOI https://doi.org/10.1051/wujns/2022274296
Published online 26 September 2022

© Wuhan University 2022

Licence Creative CommonsThis is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

0 Introduction

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

In 1990, unitary addition Cayley graph[4]Gn=Cay+(Zn,Un) was first introduced. For a positive integer n>1, Gn is the graph whose vertex set is Zn, and Zn is the ring of integers modulo n. If Un denotes set of all its units, then two vertices a and b are adjacent if and only if a+bUn. Note that Gn is |Un|-regular if |Zn| is even and (|Un|,|Un|-1)-semiregular if |Zn| is odd[5]. Some examples of Gn=Cay+(Zn,Un) are illustrated in Fig. 1.

thumbnail 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 Σ=(G,σ), where G=(V(G),E(G)) is the underlying graph of Σ and σ: E(G){+1,-1} is a signature function from the edge set E(G) into the set of {+1,-1}.

For an arbitrary edge e of Σ, if σ(e)=+1 (-1) then it is called positive (negative) edge. Moreover, Σ is said to be all-positive (all-negative) if all edges are positive (negative). Furthermore, Σ 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 vV(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 Σ are introduced.

In 1957, Harary introduced the negation[9]η(Σ) of signed graphs Σ which is obtained from Σ by negating the sign of every edge.

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

In 2006, Acharya and Sinha came up with common-edge sigraphs[8]CE(Σ). Given a sigraph Σ, its common-edge sigraph CE(Σ) is a sigraph whose vertex-set is the set of pairs of adjacent edges in Σ and two vertices of CE(Σ) are adjacent if and only if the corresponding pairs of adjacent edges of Σ 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.

thumbnail 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 Σ which is defined as follows.

Definition 1   Let G=Cay+(Zp1×Zp1α1p2α2pkαk,Φ) be a simple graph having vertex set V(G)=Zp1×Zp1α1p2α2pkαk and edge set E(G)={{x,y}:x+yΦ}, where all p1,p2,,pk are distinct prime factors and Φ is the set of all units of the ring Zp1×Zp1α1p2α2pkαk. Let Σ=(G,σ) be a signed graph whose underlying graph is G and signature function is σ:E(G){+1,-1} defined as[11]

σ ( { x , y } ) = { + 1 , i f   x φ ( p 1 )   o r   y φ ( p 1 α 1 p 2 α 2 p k α k ) ;   - 1 , o t h e r w i s e .

Examples Σ=(Cay+(Z2×Z2×3,Φ),σ) and Σ'=(Cay+(Z3×Z2×3,Φ),σ) are displayed in Fig. 3 and 4, respectively.

thumbnail Fig. 3 Σ = ( C a y + ( Z 2 × Z 2 × 3 , Φ ) , σ )

thumbnail Fig. 4 Σ ' = ( C a y + ( Z 3 × Z 2 × 3 , Φ ) , σ )

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 σ(C)=eC(σ(e)) , where eC[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 P1,P2,,Pn (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 G1=(V1,E1) is said to be isomorphic to G2=(V2,E2) if and only if there is a bijective f: V1V2 satisfied with {v1,v2}E1{f(v1),f(v2)}E2 for v1,v2V1. Analogously, Σ1 and Σ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 Σ is sign-compatible if and only if Σ does not contain a sub-sigraph isomorphic to either of the two sigraphs, S1 formed by taking the path P4=(x,u,v,y) with both edges {x,u} and {v,y} negative and the edge {u,v} positive and S2 formed by taking S1 and identifying the vertices x and y (see Fig. 5).

thumbnail 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 Σ and Derived Graphs

In this section, we discuss the balance of Σ=(G,σ) and its derived graphs η(Σ), L(Σ) and CE(Σ), where G=Cay+(Zp1×Zp1α1p2α2pkαk,Φ) and p1,p2,,pk 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 φ(n)={l:1l<n,gcd(l,n)=1}.

Lemma 4   Let Σ=(G,σ) be an addition Cayley signed graph, where G=Cay+(Zp1×Zp1α1p2α2pkαk,Φ) and all p1,p2,,pk are distinct prime factors. If one of p1,p2,,pk is 2, then Σ has exactly |Φ|2 positive edges.

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

Case 1 Suppose p1=2. In this case, Σ is disco- nnected and has exactly two connected components Σ1=(G1,σ) with vertex set V(Σ1)={(u,v): u=1 andv is odd}{(u,v): u=0 and v is even} and Σ2=(G2,σ) with vertex set V(Σ2)={(u,v): u=0 and v is odd}{(u,v):u=1 and v is even}.

Note that the underlying graph G of Σ is a |Φ| -regular graph. Hence,

| E ( Σ 1 ) | = | E ( Σ 2 ) | = 1 2 | E ( Σ ) | = 1 2 | E ( G ) | = 1 4 | Φ | p 1 α 1 + 1 p 2 α 2 p k α k

Assume {(u,v), (u',v')} is an arbitrary edge in Σ1, where (u,v){(u,v): u=1 and v is odd}, (u',v'){(u,v): u=0 and v is even} and v+v'φ(p1α1p2α2pkαk). By Definition 1, {(u,v), (u',v')} is positive edge if and only if (u,v)Φ since Φ{(u,v): u=1 and vis odd} and {(u,v):u=0 and v is even}Φ=. Moreover, if (u,v){(u,v):u=1 and v is odd}\Φ then this edge is negative. Therefore Σ1 has exactly |Φ|2 positive edges.

For any edge {(u,v), (u',v')}E(Σ2), where (u,v){(u,v): u=0 and v is odd}, (u',v'){(u,v): u=1 and v is even} and v+v'φ(p1α1p2α2pkαk). Obviously, all members of V(Σ2) are not in Φ and all edges in Σ2 are negative.

Case 2 Suppose p13 and  pi=2 for i{2,3,,k}. It is not difficult to see that Σ is connected. The vertex (0,0) is adjacent to all members of Φ, and each member of Φ is adjacent to other |Φ|-1 vertices of Σ. Moreover, those edges have at least one vertex in Φ. So there are |Φ|+|Φ|(|Φ|-1)=|Φ|2 positive edges. Let

V 1 = { ( u , v ) :   u = 0   a n d   v   i s   e v e n } { ( u , v ) :   u { 1,2 , , p 1 - 1 } a n d   v   i s   n o t   o d d - m u l t i p l e   o f   p r i m e   f a c t o r s } ;

V 2 = { ( u , v ) :   u = 0   a n d   v   i s   o d d } { ( u , v ) :   u { 1,2 , , p 1 - 1 } a n d   v   i s   o d d - m u l t i p l e   o f   p r i m e   f a c t o r s } .

Let V=V1V2. Assume (u,v) and (u',v') are arbitrary vertices of V2, the sum of v and v' is even since v and v' are both odd, hence (u,v)+(u',v')Φ. Thus none of V2 are adjacent to each other. Each vertex of V2 is adjacent to one of the vertices of V1 since Σ is connected. Let (u,v)V1 be adjacent to (u',v')V2. v should be even since v' is odd. We have (u,v)Φ and all vertices of V2 are not in Φ. All edges incident with the vertices of V2 are negative and the number is

| V 2 | × | Φ | = | V ( Σ ) | 2 | Φ | - | Φ | 2

where |V(Σ)|=p1α1+1p2α2pkαk.

The following theorem gives an equivalent charact- erization for Σ being balanced.

Theorem 1   Let Σ=(G,σ) be an addition Cayley signed graph, where G=Cay+(Zp1×Zp1α1p2α2pkαk,Φ) and all p1,p2,,pk are distinct prime factors. Then Σ is balanced if and only if one of the prime factors is 2.

Proof  

Necessity: Contrarily, assume pi3 for any i=1,2,,k. In this case, Σ is connected. Moreover, the numbers 1 and 2 are both in φ(p1) and φ(p1α1p2α2pkαk). Let us consider a cycle C=((0,1),(1,0), (1,1), (0,1)) in Σ. In fact, (0,1)+(1,0)=(1,1)Φ, the vertex (0,1) is adjacent to (1,0). Also, (1,0) is adjacent to (1,1) since (1,0)+(1,1)=(2,1)Φ. The vertex (1,1) is adjacent to (0,1) since (1,1)+(0,1)=(1,2)Φ. Note that (0,1)Φ, [(1,0)Φ] and (1,1)Φ, we have σ({(0,1), (1,0)})=-1, σ({(1,0), (1,1)})=+1, σ({(1,1), (0,1)})=+1. Then the cycle C is not positive and thus Σ is unbalanced. This is a contradiction.

Sufficiency: Suppose one of the prime factors is 2.

Case 1 Assume p1=2. Then by the proof of Lemma 4 it is known that Σ is disconnected and has exactly two connected components Σ1=(G1,σ) with vertex set V(Σ1)={(u,v): u=1 and v is odd}{(u,v): u=0 and v is even} and Σ2=(G2,σ) with vertex set V(Σ2)={(u,v): u=0 and v is odd}{(u,v):u=1 and vis even}.

For Σ2, all edges are negative since V(Σ2)Φ=. Next we prove that every cycle in Σ2 is positive. Suppose C'=(x1,x2,x3,,xm,x1) is an arbitrary cycle in Σ2. Without loss of generality, assume that x1{(u,v): u=0 and v is odd}. By Definition 1, we have x2 and xm both in {(u,v): u=1 and v is even}. Similarly, the vertices that are adjacent to x2 and xm are in {(u,v): u=0 and v is odd}. By continuing this process, it is easy to see that C' contains an even number of negative edges. Thus Σ2 is balanced.

For Σ1, let us consider an arbitrary cycle C=(x1',x2',x3',,xm',x1'). Note that every edge in Σ1 has one vertex in {(u,v): u=0 and v is even} and the other in {(u,v): u=1 and v is odd}. Without loss of generality, assume that x1'{(u,v): u=0 and v is even} then x2'{(u,v):u=1 and v is odd} and x3'{(u,v): u=0 and v is even}. Obviously, {(u,v): u=0 and v is even}Φ=. There are two following cases. If x2'Φ, then {x1',x2'} and {x2',x3'} will be positive edges. If x2'Φ, then {x1',x2'} and {x2',x3'} will be negative, which implies that the number of negative edges is even in C. Thus C is positive and Σ1 is balanced.

Case 2 Assume p13 and  pi=2 for i{2,3,,k}. Now Σ is connected. Let V(Σ)=V1V2, where

V 1 = { ( u , v ) :   u = 0   a n d   v   i s   e v e n } { ( u , v ) :   u { 1,2 , , p 1 - 1 }   a n d   v   i s   n o t   o d d - m u l t i p l e   o f   p r i m e   f a c t o r s } ;

V 2 = { ( u , v ) :   u = 0   a n d   v   i s   o d d } { ( u , v ) :   u { 1,2 , , p 1 - 1 } a n d   v   i s   o d d - m u l t i p l e   o f   p r i m e   f a c t o r s } .

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

Remark 1   If G=Cay+(Z2×Z2,Φ), then Σ=(G,σ) does not contain cycles. However, Σ is balanced. (In fact, Σ is disconnected and has exactly two connected components, say Σ1 having vertex set V(Σ1)={(0,0), (1,1)} and Σ2 having vertex set V(Σ2)={(0,1), (1,0)}. For Σ1, by definition of signature function σ, we have σ({(0,0), (1,1)})=+1 since (1,1) Φ, (0,0)Φ and (0,0) is adjacent to (1,1). For Σ2, neither of V(Σ2) is in Φ and (0,1) is adjacent to (1,0), hence σ({(0,1),(1,0)})=-1. The tree has no cycle and we can know that each tree is balanced according to the proof of Lemma 3. Σ is balanced since it is the union of two balanced trees.)

Remark 2   If G=Cay+(Z2×Z2,Φ), then it follows from Remark 1 that η(Σ) is balanced. Also, L(Σ) is an empty graph and CE(Σ) 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.

thumbnail Fig. 6 Σ = ( C a y + ( Z 2 × Z 2 , Φ ) , σ ) and its three derived graphs

Next, the balance of three derived graphs η(Σ), L(Σ) and CE(Σ) is discussed.

Lemma 5[5] G n is bipartite if and only if either n=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φ(n), then (n-i)φ(n) and if iφ(n) then (n-i)φ(n).

Theorem 2   Let Σ=(G,σ) be an addition Cayley signed graph, where G=Cay+(Zp1×Zp1α1p2α2pkαk,Φ) and all p1,p2,,pk are distinct prime factors. Then η(Σ) is balanced if and only if one of the following conditions holds:

(i) one of the prime factors is 2;

(ii) G=Cay+(Z3×Z3,Φ).

Proof  

Necessity: Contrarily, assume that pi3 for any i=1,2,,k and αi1 except for G=Cay+(Z3×Z3,Φ). The numbers 1 and 2 are both in φ(p1) and φ(p1α1p2α2pkαk). Let n1=p1α1p2α2pkαk, then we have n1-1,n1-2φ(n1) using Lemma 6. Now let us consider a cycle C=((0,0), (1,n1-2), (1,1), (0,0)) in Σ. It is not difficult to see that C is all-positive and η(C) is all-negative. Thus η(Σ) is unbalanced. This is a contradiction.

Sufficiency:

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

Case 2 Suppose G=Cay+(Z3×Z3,Φ). Obviously, η(Σ) is balanced (see Fig. 7).

thumbnail Fig. 7 Σ = ( C a y + ( Z 3 × Z 3 , Φ ) , σ ) and its derived graph η(Σ)

Lemma 7[17] Σ 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 Σ, L(Σ) is balanced if and only if the following conditions hold:

(i) for any cycle Z in Σ,

(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 vV(Σ), if d(v)>2, then there is at most one negative edge incident at v in Σ.

Theorem 3   Let Σ=(G,σ) be an addition Cayley signed graph, where G=Cay+(Zp1×Zp1α1p2α2pkαk,Φ) and all p1,p2,,pk are distinct prime factors. Then L(Σ) is balanced if and only if Σ is balanced.

Proof  

Necessity: Contrarily, assume that Σ is unbalanced. By Theorem 1, we have pi3 for any i=1,2,,k. In this case, we have d(v)|Φ|-1 which is greater than 2 for all vertices. Note that (0,1) is adjacent to vertices (1,0), (2,0),, (p1-1,0) respectively. None of these p1 vertices is in Φ, hence d-((0,1))p1-1. p13. It follows from Lemma 8 that L(Σ) is unbalanced. This is a contradiction.

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

Lemma 9[8] For any sigraph Σ, CE(Σ) is bala- nced if and only if Σ is a balanced sigraph such that for every vertex vV(Σ) with d(v)3,

(i) if d(v)>3 then d-(v)=0;

(ii) if d(v)=3 then d-(v)=0 or d-(v)=2; and

(iii) for every path P4=(x,v,w,y) of length three, {v,w} is a positive edge in Σ.

Theorem 4   Let Σ=(G,σ) be an addition Cayley signed graph, where G=Cay+(Zp1×Zp1α1p2α2pkαk,Φ) and all p1,p2,,pk are distinct prime factors. Then CE(Σ) is balanced if and only if one of the following conditions holds:

(i) |Φ|=1, i.e. G=Cay+(Z2×Z2,Φ);

(ii) |Φ|=2, i.e. G=Cay+(Z2×Z22,Φ) or G=Cay+(Z2×Z2×3,Φ).

Proof  

Necessity: Contrarily, assume that G=Cay+(Zp1×Zp1α1p2α2pkαk,Φ) and |Φ|3. Now there are the following three cases.

Case 1 Suppose p1=2. Clearly, Σ is disconnected and has two connected components Σ1=(G1,σ) having vertex set V(Σ1)={(u,v): u=1 and v is odd}{(u,v): u=0 and v is even} and Σ2=(G2,σ) having vertex set V(Σ2)={(u,v): u=0 and v is odd}{(u,v):u=1 and v is even}.

According to the proof of Theorem 1, Σ1 is balan- ced. By Lemma 7, Σ1 can be considered all-positive, thus CE(Σ1) is balanced. For Σ2, the degrees of all members in V(Σ2) are negative and greater than 3 since Σ2 is all-negative. Thus the condition (i) and (ii) of Lemma 9 does not hold for Σ2, which implies that CE(Σ) is unbalanced. This is a contradiction.

Case 2 Suppose p13 and  pi=2, for i=2,3,,k. In this case, |Φ|>3, Σ is a connected and |Φ|-regular graph. Let V(Σ)=V1V2, where

V 1 = { ( u , v ) :   u = 0   a n d   v   i s   e v e n } { ( u , v ) :   u { 1,2 , , p 1 - 1 }  

a n d   v   i s   n o t   o d d -multiple of prime factors};

V 2 = { ( u , v ) :   u = 0   a n d   v   i s   o d d } { ( u , v ) :   u { 1,2 , , p 1 - 1 }

a n d   v   i s   o d d -multiple of prime factors}.

It follows from the proof of Lemma 4 that any two vertices in V2 are not adjacent. Then there exists an edge {(u,v), (u',v')} whose one vertex in V1 and the other in V2 since Σ is connected. Note that d((u',v'))=|Φ|>3, and by the proof of Lemma 4, {(u,v), (u',v')} is negative. Therefore, it follows from Lemma 9 (i) that CE(Σ) is unbalanced. This a contradiction.

Case 3 Suppose that pi3 for all i=1,2,,k. In this case, 2φ(p1) and φ(p1α1p2α2pkαk) and |Φ|4. Then d(v)3 for any vV(Σ). Note that the vertex (0,1) is adjacent to (1,0), (2,0),, (p1-1,0) and all p1-1 edges are negative. Also, d((0,1))=|Φ|4 since (0,1)Φ. Thus the condition (i) of Lemma 9 does not hold for (0,1), which implies that CE(Σ) is unbalanced. This is a contradiction.

Sufficiency: It can be concluded that CE(Σ) is balanced in the following three cases.

Case 1 Let G=Cay+(Z2×Z2,Φ). In this case, |Φ|=1. According to Remark 2, CE(Σ) is balanced.

Case 2 Let G=Cay+(Z2×Z2×3,Φ) (see Fig. 3). In this case, |Φ|=2. Obviously, CE(Σ) is balanced (see Fig. 8).

thumbnail Fig. 8 The derived graph CE(Σ) of Σ=(Cay+(Z2×Z2×3,Φ,σ)

Case 3 Let G=Cay+(Z2×Z22,Φ). In this case, |Φ|=2. From Theorem 1, Σ is balanced, and Σ can be considered all-positive according to Lemma 7. Therefore CE(Σ) is balanced.

3 Clusterability and Sign-Compatibility of Σ

In this section, we give a necessary and sufficient condition for Σ being clusterable and a sufficient cond- ition for Σ being sign-compatible.

Theorem 5   Let Σ=(G,σ) be an addition Cayley signed graph, where G=Cay+(Zp1×Zp1α1p2α2pkαk,Φ) and all p1,p2,,pk are distinct prime factors. Then Σ is clusterable if and only if Σ is balanced.

Proof  

Necessity: Contrarily, assume that Σ is unbalanced. From Theorem 1, we have pi3 for any i=1,2,,k. Let us consider a cycle C=((0,1), (1,0),(1,1), (0,1)). It follows from Lemma 1 that Σ is not clust- erable since the cycle C contains only one negative edge {(0,1), (1,0)}. This is a contradiction.

Sufficiency: Let Σ be balanced. Then every cycle in Σ is positive. This implies every cycle of Σ has either all positive edges or an even number of negative edges. Thus the required result can be concluded from Lemma 1.

Theorem 6   Let Σ=(G,σ) be an addition Cayley signed graph, where G=Cay+(Zp1×Zp1α1p2α2pkαk,Φ) and all p1,p2,,pk are distinct prime factors. Then Σ is always sign-compatible.

Proof   Contrarily, assume that Σ is not signcompatible. According to Lemma 2, Σ contains a sub-sigraph isomorphic to either S1 or S2 (see Fig. 5).

Case 1 Suppose that Σ contains a sub-sigraph isomophic to S1. Denote by P4=((x1,y1), (x2,y2),(x3,y3), (x4,y4)) the path with σ({(x1,y1), (x2,y2)})=-1, σ({(x2,y2), (x3,y3)})=+1 and σ({(x3,y3), (x4,y4)})=-1. Notice that the vertices (x2,y2) and (x3,y3) can not be in Φ at the same time, otherwise P4 is all-positive. Without loss of generality, let (x2,y2)Φ and (x3,y3)Φ. Then σ({(x1,y1), (x2,y2)})=+1 and σ({(x2,y2), (x3,y3)})=+1 which is contradictary to the choice of P4. Thus Σ can not contain a sub-sigraph isomorphic to S1.

Case 2 Assume that Σ contains a sub-sigraph iso- morphic to S2. In this case, the required result can be concluded completely similar to Case 1 since we need only consider (x1,y1)=(x4,y4).

Therefore Σ is always sign-compatible.

References

  1. Cayley A. On the theory of groups [J]. Proceedings of the London Mathematical Society, 1878, 9: 126-233. [Google Scholar]
  2. Biggs N. Algebraic Graph Theory [M]. Cambridge: Cambridge University Press, 1993. [Google Scholar]
  3. Godsil C, Royle G F. Algebraic Graph Theory [M]. Berlin: Springer Science and Business Media, 2001. [CrossRef] [Google Scholar]
  4. Grimaldi R P. Graph from rings [J]. Congr Numer, 1990, 71: 95-104. [MathSciNet] [Google Scholar]
  5. Sinha D, Garg P, Singh A. Some properties of unitary additi- on Cayley graphs [J]. Notes on Number Theory and Discrete Mathematics, 2011, 17(3): 49-59. [Google Scholar]
  6. Harary F. On the notion of balance of a signed graph [J]. Michigan Mathematical Journal, 1953, 2(2): 143-146. [Google Scholar]
  7. Behzad M, Chartrand G. Line-coloring of signed graphs [J]. Elemente der Mathematik, 1969, 24(3): 49-52. [Google Scholar]
  8. Acharya M, Sinha D. Common-edge sigraphs [J]. AKCE International Journal of Graphs and Combinatorics, 2006, 3(2): 115-130. [MathSciNet] [Google Scholar]
  9. Harary F. Structural duality [J]. Behavioral Science, 1957, 2(4): 255-265. [Google Scholar]
  10. Iranmanesh M A, Moghaddami N. Some properties of Cayley signed graphs on finite abelian groups [EB/OL]. [2020-11-10]. https://doi.org/10.48550/arXiv.2011.05753. [Google Scholar]
  11. Sinha D, Garg P. On the unitary Cayley signed graphs [J]. The Electronic Journal of Combinatorics, 2011, 18(1): 2290-2296. [Google Scholar]
  12. Hou Y P, Li J S, Pan Y L. On the Laplacian eigenvalues of signed graphs [J]. Linear and Multilinear Algebra, 2003, 51(1): 21-30. [CrossRef] [MathSciNet] [Google Scholar]
  13. Davis J A. Clustering and structural balance in graphs [J]. Human Relations, 1967, 20(2): 181-187. [Google Scholar]
  14. Sinha D, Dhama A. Sign-compatibility of some derived sig- ned graphs [J]. Indian Journal of Mathematics, 2012, 11(4): 1-14. [Google Scholar]
  15. Zaslavsky T. Signed graphs [J]. Discrete Applied Mathematics, 1982, 4(1): 47-74. [CrossRef] [MathSciNet] [Google Scholar]
  16. Sinha D, Dhama A, Acharya B D. Unitary addition Cayley signed graphs [J]. European Journal of Pure and Applied Mathematics, 2013, 6(2): 189-210. [MathSciNet] [Google Scholar]
  17. Zaslavsky T. Matrices in the theory of signed simple graphs [J]. Mathematics, 2013(3): 207-229. [Google Scholar]
  18. Acharya M, Sinha D. A characterization of sigraphs whose line sigraphs and jump sigraphs are switching equivalent [J]. Electronic Notes in Discrete Mathematics, 2003, 15: 12. [CrossRef] [Google Scholar]

All Figures

thumbnail Fig. 1 Some examples of addition Cayley graphs
In the text
thumbnail Fig. 2 The example of signed graphs and its derived graphs
In the text
thumbnail Fig. 3 Σ = ( C a y + ( Z 2 × Z 2 × 3 , Φ ) , σ )
In the text
thumbnail Fig. 4 Σ ' = ( C a y + ( Z 3 × Z 2 × 3 , Φ ) , σ )
In the text
thumbnail Fig. 5 Forbidden subsigraphs for a sign-compatible sigraph
In the text
thumbnail Fig. 6 Σ = ( C a y + ( Z 2 × Z 2 , Φ ) , σ ) and its three derived graphs
In the text
thumbnail Fig. 7 Σ = ( C a y + ( Z 3 × Z 3 , Φ ) , σ ) and its derived graph η(Σ)
In the text
thumbnail Fig. 8 The derived graph CE(Σ) of Σ=(Cay+(Z2×Z2×3,Φ,σ)
In the text

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.