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 |
Mathematics
CLC number: O 157.5
Some Properties of a Class of Addition Cayley Signed Graph
Department of Mathematics, Lanzhou Jiaotong University, Lanzhou 730070, Gansu, China
† To whom correspondence should be addressed. E-mail: wangwzh @mail.lzjtu. cn
Received:
10
March
2022
Let be a simple graph having vertex set and edge set , where all are distinct prime factors and is the set of all units of the ring be a signed graph whose underlying graph is and signature function is defined as In this paper, we characterize the balance of and some graphs derived from it such as , and . Moreover, we investigate the clusterability and sign-compativility of .
Key words: signed graphs / derived graph / balance / clusterability / sign-compatibility
Biography: YUAN Yuqing, female, Master candidate, research direction: algebraic graph theory. E-mail: szyyq0924@163.com
Fundation item: Supported by the National Natural Science Foundation of China (11561042,11961040) and the Natural Science Foundation of Gansu Province (20JR5RA 418)
© Wuhan University 2022
This 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 is a non-empty subset which does not contain the identity element 1 of . The Cayley graph[1] is a graph having vertex set and edge set . For further information about Cayley graphs, one may refer to Refs.[2,3].
In 1990, unitary addition Cayley graph[4] was first introduced. For a positive integer , is the graph whose vertex set is , and is the ring of integers modulo . If denotes set of all its units, then two vertices and are adjacent if and only if . Note that is -regular if is even and -semiregular if is odd[5]. Some examples of 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 , where is the underlying graph of and is a signature function from the edge set into the set of .
For an arbitrary edge of , if 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 denoted by which is the number of positive (negative) edges associates to and the degree of is . 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] 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 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]. Given a sigraph , its common-edge sigraph is a sigraph whose vertex-set is the set of pairs of adjacent edges in and two vertices of 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.
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 be a simple graph having vertex set and edge set , where all are distinct prime factors and is the set of all units of the ring . Let be a signed graph whose underlying graph is and signature function is defined as[11]
Examples and are displayed in Fig. 3 and 4, respectively.
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 is given by , where [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 (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 is said to be isomorphic to if and only if there is a bijective satisfied with for . Analogously, and 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, formed by taking the path with both edges and negative and the edge positive and formed by taking and identifying the vertices and (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 and Derived Graphs
In this section, we discuss the balance of and its derived graphs , and , where and 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 , let .
Lemma 4 Let be an addition Cayley signed graph, where and all are distinct prime factors. If one of is 2, then has exactly positive edges.
Proof Since one of the prime factors is 2 then there are two following cases.
Case 1 Suppose . In this case, is disco- nnected and has exactly two connected components with vertex set and with vertex set .
Note that the underlying graph of is a -regular graph. Hence,
Assume is an arbitrary edge in , where , and . By Definition 1, is positive edge if and only if since and . Moreover, if then this edge is negative. Therefore has exactly positive edges.
For any edge , where , and . Obviously, all members of are not in and all edges in are negative.
Case 2 Suppose and for . It is not difficult to see that is connected. The vertex is adjacent to all members of , and each member of is adjacent to other vertices of . Moreover, those edges have at least one vertex in . So there are positive edges. Let
Let . Assume and are arbitrary vertices of , the sum of and is even since and are both odd, hence . Thus none of are adjacent to each other. Each vertex of is adjacent to one of the vertices of since is connected. Let be adjacent to . should be even since is odd. We have and all vertices of are not in . All edges incident with the vertices of are negative and the number is
where .
The following theorem gives an equivalent charact- erization for being balanced.
Theorem 1 Let be an addition Cayley signed graph, where and all are distinct prime factors. Then is balanced if and only if one of the prime factors is 2.
Proof
Necessity: Contrarily, assume for any . In this case, is connected. Moreover, the numbers 1 and 2 are both in and . Let us consider a cycle in . In fact, , the vertex is adjacent to . Also, is adjacent to since . The vertex is adjacent to since . Note that and , we have , , . Then the cycle is not positive and thus is unbalanced. This is a contradiction.
Sufficiency: Suppose one of the prime factors is 2.
Case 1 Assume . Then by the proof of Lemma 4 it is known that is disconnected and has exactly two connected components with vertex set and with vertex set .
For , all edges are negative since . Next we prove that every cycle in is positive. Suppose is an arbitrary cycle in . Without loss of generality, assume that . By Definition 1, we have and both in . Similarly, the vertices that are adjacent to and are in . By continuing this process, it is easy to see that contains an even number of negative edges. Thus is balanced.
For , let us consider an arbitrary cycle . Note that every edge in has one vertex in and the other in . Without loss of generality, assume that then and . Obviously, . There are two following cases. If , then and will be positive edges. If , then and will be negative, which implies that the number of negative edges is even in . Thus is positive and is balanced.
Case 2 Assume and for . Now is connected. Let , where
Suppose is an arbitrary cycle in . If all edges of are positive, then is positive. If contains a negative edge , then this edge has one vertex in and the other in from the proof of Lemma 4. Without loss of generality, assume that and . Next, we will prove that another negative edge which associates to is required. Let above edge be . Neither of the vertices of is adjacent to each other, since is connected. and is odd. is even and is not in . Therefore is negative, and the negative occurs in pairs. It is easy to conclude that is positive. Thus is balanced.
Remark 1 If , then does not contain cycles. However, is balanced. (In fact, is disconnected and has exactly two connected components, say having vertex set and having vertex set . For , by definition of signature function , we have since , and is adjacent to . For , neither of is in and is adjacent to , hence . 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 , then it follows from Remark 1 that is balanced. Also, is an empty graph and 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 and its three derived graphs |
Next, the balance of three derived graphs , and is discussed.
Lemma 5[5] is bipartite if and only if either or 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 , if , then and if then .
Theorem 2 Let be an addition Cayley signed graph, where and all 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) .
Proof
Necessity: Contrarily, assume that for any and except for . The numbers 1 and 2 are both in and . Let , then we have , using Lemma 6. Now let us consider a cycle in . It is not difficult to see that is all-positive and 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 . Obviously, is balanced (see Fig. 7).
Fig. 7 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 , is balanced if and only if the following conditions hold:
(i) for any cycle in ,
(a) if is all-negative, then has even length;
(b) if is heterogeneous, then has an even number of negative sections with even length;
(ii) for , if , then there is at most one negative edge incident at in .
Theorem 3 Let be an addition Cayley signed graph, where and all are distinct prime factors. Then is balanced if and only if is balanced.
Proof
Necessity: Contrarily, assume that is unbalanced. By Theorem 1, we have for any . In this case, we have which is greater than 2 for all vertices. Note that is adjacent to vertices respectively. None of these vertices is in , hence . . It follows from Lemma 8 that is unbalanced. This is a contradiction.
Sufficiency: Assume that is balanced. According to Lemma 7, can be considered all-positive. Therefore is all-positive and balanced.
Lemma 9[8] For any sigraph , is bala- nced if and only if is a balanced sigraph such that for every vertex with ,
(i) if then ;
(ii) if then or ; and
(iii) for every path of length three, is a positive edge in .
Theorem 4 Let be an addition Cayley signed graph, where and all are distinct prime factors. Then is balanced if and only if one of the following conditions holds:
(i) , i.e. ;
(ii) , i.e. or .
Proof
Necessity: Contrarily, assume that and . Now there are the following three cases.
Case 1 Suppose . Clearly, is disconnected and has two connected components having vertex set and having vertex set .
According to the proof of Theorem 1, is balan- ced. By Lemma 7, can be considered all-positive, thus is balanced. For , the degrees of all members in are negative and greater than 3 since is all-negative. Thus the condition (i) and (ii) of Lemma 9 does not hold for , which implies that is unbalanced. This is a contradiction.
Case 2 Suppose and , for . In this case, , is a connected and -regular graph. Let , where
-;
-.
It follows from the proof of Lemma 4 that any two vertices in are not adjacent. Then there exists an edge whose one vertex in and the other in since is connected. Note that , and by the proof of Lemma 4, is negative. Therefore, it follows from Lemma 9 (i) that is unbalanced. This a contradiction.
Case 3 Suppose that for all . In this case, and and . Then for any . Note that the vertex is adjacent to and all edges are negative. Also, since . Thus the condition (i) of Lemma 9 does not hold for , which implies that is unbalanced. This is a contradiction.
Sufficiency: It can be concluded that is balanced in the following three cases.
Case 1 Let . In this case, . According to Remark 2, is balanced.
Case 2 Let (see Fig. 3). In this case, . Obviously, is balanced (see Fig. 8).
Fig. 8 The derived graph of |
Case 3 Let . In this case, . From Theorem 1, is balanced, and can be considered all-positive according to Lemma 7. Therefore 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 be an addition Cayley signed graph, where and all 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 for any . Let us consider a cycle . It follows from Lemma 1 that Σ is not clust- erable since the cycle contains only one negative edge . 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 be an addition Cayley signed graph, where and all 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 or (see Fig. 5).
Case 1 Suppose that contains a sub-sigraph isomophic to . Denote by the path with , and . Notice that the vertices and can not be in at the same time, otherwise is all-positive. Without loss of generality, let and . Then and which is contradictary to the choice of . Thus can not contain a sub-sigraph isomorphic to .
Case 2 Assume that contains a sub-sigraph iso- morphic to . In this case, the required result can be concluded completely similar to Case 1 since we need only consider .
Therefore is always sign-compatible.
References
- Cayley A. On the theory of groups [J]. Proceedings of the London Mathematical Society, 1878, 9: 126-233. [Google Scholar]
- Biggs N. Algebraic Graph Theory [M]. Cambridge: Cambridge University Press, 1993. [Google Scholar]
- Godsil C, Royle G F. Algebraic Graph Theory [M]. Berlin: Springer Science and Business Media, 2001. [CrossRef] [Google Scholar]
- Grimaldi R P. Graph from rings [J]. Congr Numer, 1990, 71: 95-104. [MathSciNet] [Google Scholar]
- 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]
- Harary F. On the notion of balance of a signed graph [J]. Michigan Mathematical Journal, 1953, 2(2): 143-146. [Google Scholar]
- Behzad M, Chartrand G. Line-coloring of signed graphs [J]. Elemente der Mathematik, 1969, 24(3): 49-52. [Google Scholar]
- Acharya M, Sinha D. Common-edge sigraphs [J]. AKCE International Journal of Graphs and Combinatorics, 2006, 3(2): 115-130. [MathSciNet] [Google Scholar]
- Harary F. Structural duality [J]. Behavioral Science, 1957, 2(4): 255-265. [Google Scholar]
- 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]
- Sinha D, Garg P. On the unitary Cayley signed graphs [J]. The Electronic Journal of Combinatorics, 2011, 18(1): 2290-2296. [Google Scholar]
- 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]
- Davis J A. Clustering and structural balance in graphs [J]. Human Relations, 1967, 20(2): 181-187. [Google Scholar]
- Sinha D, Dhama A. Sign-compatibility of some derived sig- ned graphs [J]. Indian Journal of Mathematics, 2012, 11(4): 1-14. [Google Scholar]
- Zaslavsky T. Signed graphs [J]. Discrete Applied Mathematics, 1982, 4(1): 47-74. [CrossRef] [MathSciNet] [Google Scholar]
- 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]
- Zaslavsky T. Matrices in the theory of signed simple graphs [J]. Mathematics, 2013(3): 207-229. [Google Scholar]
- 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
Fig. 1 Some examples of addition Cayley graphs | |
In the text |
Fig. 2 The example of signed graphs and its derived graphs | |
In the text |
Fig. 5 Forbidden subsigraphs for a sign-compatible sigraph | |
In the text |
Fig. 6 and its three derived graphs | |
In the text |
Fig. 7 and its derived graph | |
In the text |
Fig. 8 The derived graph of | |
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.