compiles/be29784c162a00b0bbcf92378a8261cf/output.dvi EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 6, No. 2, 2013, 189-210 ISSN 1307-5543 – www.ejpam.com Unitary Addition Cayley Signed Graphs Deepa Sinha 1, Ayushi Dhama 2,∗, B.D. Acharya 3 1 South Asian University, Akbar Bhawan, Chankyapuri, New Delhi-110 021, India 2 Centre for Mathematical Sciences, Banasthali University, Banasthali-304 022 Rajasthan, India 3 Centre For Excellence in Interdisciplinary Mathematics, M.E.R.I.T., A/9, USO Road, Shaheed Jit Singh Marg, Qutab Institutional Area, New Delhi - 100 067, India. Abstract. A signed graph (or sigraph in short) is an ordered pair S = (Su,σ), where Su is a graph G = (V, E) and σ : E→ {+,−} is a function from the edge set E of Su into the set {+,−}. For a positive integer n, the unitary addition Cayley graph Gn is the graph whose vertex set is Zn, the ring of integers modulo n and if Un denotes set of all units of the ring, then two vertices a and b are adjacent if and only if a+ b ∈ Un. For a positive integer n, the unitary addition Cayley sigraph Σn = (Σ u n ,σ) is defined as the sigraph, where Σu n is the unitary addition Cayley graph and for an edge ab of Σn, σ(ab) = ¨ + if a ∈ Un or b ∈ Un, − otherwise. In this paper, we have obtained a characterization of balanced and clusterable unitary addition Cayley sigraphs. Further, we have established a characterization of canonically consistent unitary addition Cayley sigraphs Σn, where n has at most two distinct odd prime factors. 2010 Mathematics Subject Classifications: 05C22; 05C75 Key Words and Phrases: sigraph, balance, clustering, C−consistency, unitary Cayley sigraph, unitary addition Cayley graph, unitary addition Cayley sigraph 1. Introduction For standard terminology and notation in graph theory, we refer the reader to Harary [30] and West [45] and to Zaslavsky [46, 47] for sigraphs. Throughout the text, we consider finite, undirected graphs with no loops or multiple edges. ∗Corresponding author. Email addresses: deepa_sinha2001@yahoo.com (D. Sinha), ayushi.dhama2@gmail.com (A. Dhama), devadas.acharya@gmail.com (B. Acharya) http://www.ejpam.com 189 c© 2013 EJPAM All rights reserved. D. Sinha, A. Dhama, B. Acharya / Eur. J. Pure Appl. Math, 6 (2013), 189-210 190 1.1. Sigraphs and Some Basic Notions and Notations A signed graph (or, sigraph in short; see [29]) is an ordered pair S = (Su,σ), where Su is a graph G = (V, E), called the underlying graph of S and σ : E → {+,−} is a function from the edge set E of Su into the set {+,−}, called the signature of S. Let E+(S) = {e ∈ E(G) : σ(e) = +} and E−(S) = {e ∈ E(G) : σ(e) =−}. The elements of E+(S) and E−(S) are called positive and negative edges of S, respectively. A sigraph is all-positive (all-negative) if all its edges are positive (negative); further, it is said to be homogeneous if it is either all-positive or all-negative and heterogeneous otherwise. The positive (negative) degree of a vertex v ∈ V (S) denoted by d+(v)(d−(v)) is the number of positive (negative) edges incident on the vertex v and d(v) = d+(v)+ d−(v). The negation η(S) of a sigraph S is a sigraph obtained from S by negating the sign of every edge of S, in the sense that to find η(S) we change the sign of every edge to its opposite in S. A positive (negative) section of a subsigraph S′ of a sigraph S is a maximal edge-induced connected subsigraph in S consisting of only the positive (negative) edges of S; in particular, a positive (negative) section in a heterogeneous cycle of S is essentially a maximal all-positive (all-negative) path in the cycle. Two graphs G1 = (V1, E1) and G2 = (V2, E2) are isomorphic if there is a bijective function f : V1 → V2 such that for all v1, v2 ∈ V : v1v2 ∈ E1⇔ f (v1) f (v2) ∈ E2. Two sigraphs S1 and S2 are isomorphic if there is an isomorphism between their underlying graphs that preserves edge signs. A cycle in a sigraph S is said to be positive if it contains an even number of negative edges. A given sigraph S is said to be balanced if every cycle in S is positive (see [29]); balanced sigraphs were first defined and characterized by Harary [29]. A spectral characterization of balanced sigraphs was given by Acharya [1]. Harary and Kabell [31, 32] developed a simple algorithm to detect balanced sigraphs and also enumerated them. 1.2. The Notion of Balance in a Sigraph Harary [29] derived the following structural criterion called partition criterion for balance in sigraphs. Theorem 1 ([29]). A sigraph S is balanced if and only if its vertex set V (S) can be partitioned into two subsets V1 and V2, one of them possibly empty, such that every positive edge joins two vertices in the same subset and every negative edge joins two vertices from different subsets. The following important lemma on balanced sigraphs is given by Zaslavsky: D. Sinha, A. Dhama, B. Acharya / Eur. J. Pure Appl. Math, 6 (2013), 189-210 191 Lemma 1 ([48]). A sigraph in which every chordless cycle is positive, is balanced. 1.3. The Notion of Clustering in a Sigraph A signed graph is said to be clusterable if its vertex set can be partitioned into pairwise disjoint subsets, called clusters, such that every negative edge joins vertices in different clusters and every positive edge joins vertices in the same cluster; we shall call such a partition a Davis partition, after its originator [19], or a clustering [16]. Clearly, every graph, treated as an all- positive sigraph, is clusterable with its entire vertex set forming a single cluster. Next, every heterogeneous sigraph is balanced if and only if it is clusterable with exactly two clusters [29]; this particular Davis partition is known as Harary bipartition [46]. Davis [19] characterized clusterable signed graphs as precisely those in which no cycle has exactly one negative edge (also, see [16]). Theorem 2 ([19]). A siraph S is clusterable if and only if S contains no cycle with exactly one negative edge. 1.4. The Notions of Consistency and Sign-Compatibility in a Sigraph A marked sigraph is an ordered pair Sµ = (S,µ) where S = (Su,σ) is a sigraph and µ : V (Su)→ {+,−} is a function from the vertex set V (Su) of Su into the set {+,−}, called a marking of S. A cycle Z in Sµ is said to be consistent if it contains an even number of negative vertices. A given sigraph S is said to be consistent if every cycle in it is consistent [2]; for digraphs, the notion was due to Beineke and Harary [11, 12]. In particular, σ induces a unique marking µσ defined by µσ(v) = ∏ e j∈Ev σ(e j), v ∈ V (S), is called the canonical marking (or, C -marking in short) of S, where Ev is the set of edges e j incident at v in S [40]. Now, if every vertex of a given sigraph S is canonically marked, then a cycle Z in S is said to be canonically consistent (C -consistent) if it contains an even number of negative vertices and the given sigraph S is said be C -consistent if every cycle in it is C -consistent. Thus, the original notion of consistent graphs due to Beineke and Harary [11, 12] reduces to that of trivial C -consistency, when all the vertices receive ‘+’. Although consistent digraphs were neatly characterized in [11, 12], the problem of characterizing consistent marked graphs was declared open by Beineke and Harary [11]; subsequently, it was solved successfully by many authors (see [46] for a comprehensive appraisal). However, characterization of C -consistent sigraphs is still an open problem. D. Sinha, A. Dhama, B. Acharya / Eur. J. Pure Appl. Math, 6 (2013), 189-210 192 A sigraph S is sign-compatible [40] if there exists a marking µ of its vertices such that the end vertices of every negative edge receive ‘-1’ marks in µ and no positive edge in S has both of its ends assigned ‘-1’ marks in µ. sign-incompatible otherwise. The notion of sign-compatibility arises naturally in the characterization of line sigraphs [5]. 1.5. Some Notions of Derived Sigraphs There are many notions of sigraphs derived from a given sigraph, generically addressed here as ‘derived sigraphs’. Some of them considered in our investigations include the follow- ing ones. For a sigraph S, Behzad and Chartrand [10] defined its line sigraph, L(S) as the sigraph in which the edges of S are represented as vertices, two of these vertices are defined adjacent whenever the corresponding edges in S have a vertex in common, any such edge e f is defined to be negative whenever both e and f are negative edges in S. For a sigraph S, Gill [24] defined its×-line sigraph L×(S) as follows: the L×(S) is a sigraph defined on the line graph L(Su) of the graph Su by assigning to each edge e f of L(Su), the product of signs of the adjacent edges e and f of S. For a sigraph S, Acharya and Sinha [6] defined its common-edge sigraph CE(S) as the si- graph whose vertex set is the set of pairs of adjacent edges in S and two vertices of CE(S) are adjacent if the corresponding pairs of adjacent edges of S have exactly one edge in common, with the sign same as that of their common edge. The semi-total line graph T1(G) [38] of a graph G is the graph whose vertex set is V (G)∪ E(G) where V (G) and E(G) are vertex set and edge set of G, respectively and in T1(G) two vertices are adjacent if and only if (i) they are adjacent edges in G, or (ii) one is a vertex and the other is an edge in G incident to it. Sinha et al. [44] extended this notion of semi-total line graphs to the theory of sigraphs as follows: Let S = (V, E,σ) be any sigraph. Its semi-total line sigraph T1(S) has T1(S u) as its underlying graph and for any edge uv of T1(S u), σT1 (uv) = ( σ(u)σ(v) if u, v ∈ E, σ(v) if u ∈ V and v ∈ E. 1.6. Unitary Cayley Graph and its Sigraph Varieties Let Γ be a group and B be a subset of Γ such that B does not contain the identity of Γ. Assume B−1 = {b−1 : b ∈ B} = B. The Cayley graph X ′ = Ca y(Γ, B) is an undirected graph D. Sinha, A. Dhama, B. Acharya / Eur. J. Pure Appl. Math, 6 (2013), 189-210 193 having vertex set V (X ′) = Γ and edge set E(X ′) = {ab : ab−1 ∈ B}, where a, b ∈ Γ. The Cay- ley graph X ′ is a regular graph of degree |B|. Its connected components are the right cosets of the subgroup generated by B. Therefore, if B generates Γ, then X ′ is a connected graph. The books on algebraic graph theory by Biggs [14] and by Godsil and Royle [25] provide many information regarding Cayley graphs. For a positive integer n, the unitary Cayley graph Xn is the graph whose vertex set is Zn, the ring of integers modulo n and if Un denotes set of all its units then two vertices a and b are adjacent if and only if (a − b) ∈ Un. The unitary Cayley graph Xn is then the same as Xn = Ca y(Zn, Un). The structure and various properties of unitary Cayley graphs have been studied in literature (see [7, 9, 13, 15, 20–23, 34, 37, 39]). Let Γ be an abelian group and B be a subset of Γ. The addition Cayley graph G′ = Ca y+(Γ, B) is the graph having the vertex set V (G′) = Γ and the edge set E(G′) = {ab : a+ b ∈ B}, where a, b ∈ Γ. Several properties of addition Cayley graphs have been discussed in literature (see [8, 17, 18, 26–28, 35, 36]). For a positive integer n, the unitary addition Cayley graph Gn is the graph whose vertex set is Zn, the integers modulo n and if Un denotes set of all units of the ring Zn, then two vertices a and b are adjacent if and only if a+ b ∈ Un. The unitary addition Cayley graph Gn may also be defined as, Gn = Ca y+(Zn, Un). Some properties of unitary addition Cayley graphs have been studied in literature (see [43]). Theorem 3 ([43]). The unitary addition Cayley graph Gn is isomorphic to the unitary Cayley graph Xn if and only if n is even. Some examples of unitary addition Cayley graphs are displayed in Figure 1. Our aim in this paper is to introduce an extension of the notion of unitary addition Cayley graphs in a natural way to the theory of sigraphs and study their fundamental properties. 2. Unitary Addition Cayley Sigraphs We introduce the definition of a unitary addition Cayley sigraph as follows: Definition 1. For a positive integer n, the unitary addition Cayley sigraph Σn = (Σ u n,σ) is defined as the sigraph, where Σu n is the unitary addition Cayley graph and for an edge ab of Σn, σ(ab) = ( + if a ∈ Un or b ∈ Un, − otherwise. D. Sinha, A. Dhama, B. Acharya / Eur. J. Pure Appl. Math, 6 (2013), 189-210 194 0 1 (a) G2 (b) G3 0 1 23 (c) G4 0 1 2 3 4 (d) G5 0 1 2 3 45 (e) G6 0 1 2 3 4 5 6 (f) G7 Figure 1: Some examples of unitary addition Cayley graphs 0 2 3 4 1 (a) Σ5 0 1 2 3 45 (b) Σ6 (c) Σ10 Figure 2: Some examples of unitary addition Cayley sigraphs Three examples of unitary addition Cayley sigraphs for n = 5,6,10 are displayed as (a), (b) and (c) respectively in Figure 2. Throughout the text, we consider n≥ 2. D. Sinha, A. Dhama, B. Acharya / Eur. J. Pure Appl. Math, 6 (2013), 189-210 195 Theorem 4 ([43]). Let m be any vertex of the unitary addition Cayley graph Gn. Then, d(m) = ( φ(n)− 1 if n is odd and (m, n) = 1. φ(n) otherwise . where φ(n) denotes the Euler totient function that gives the number of primes not exceeding n. Lemma 2. For an integer n, if i ∈ Un then (n− i) ∈ Un and if i 6∈ Un then (n− i) 6∈ Un. Proof. Suppose n is any integer. Then, i ∈ Un ⇒ (n, i) = 1, where (n, i) is gcd(n, i). We want to show that (n− i) ∈ Un. Suppose, on the contrary, (n− i) 6∈ Un. Then, (n, n− i) = k ⇒ k | n and k | (n− i), whence n = αk and (n− i) = βk. But, n = αk gives αk− i = βk⇒ (α− β)k = i ⇒ k | i. Thus, k | i and k | n imply (n, i) 6= 1, a contradiction to our hypothesis. Hence, if i ∈ Un then (n− i) ∈ Un. Next, suppose i 6∈ Un. Then, (n− i) ∈ Un⇒ (n, (n− i)) = 1. As i 6∈ Un⇒ 1 6= (n, i) = l ⇒ l | n and l | i ⇒ n = αl and i = β l. This shows that n− i = αl − β l ⇒ (α− β)l ⇒ l | (n− i). Thus, l | n and l | (n− i) imply (n, (n− i)) 6= 1, a contradiction to the hypothesis. Hence, by contraposition, if i 6∈ Un then (n− i) 6∈ Un. Thus, the result follows. Theorem 5. The unitary addition Cayley sigraph Σn = (Σ u n,σ1) is isomorphic to the unitary Cayley sigraph Sn = (S u n,σ2) if and only if n is even. Proof. Necessity: Suppose Σn ∼= Sn. Then, Σu n ∼= Su n, whence the proof follows by Theo- rem 3. Sufficiency: Suppose n is even. Then, by Theorem 3, we get Σu n ∼= Su n. Now, consider a function f : V (Gn)→ V (Xn) such that f (m) = ( m if m is even n−m if m is odd. Let Un = {a1, a2, . . . , aφ(n)}. Since the vertex m is adjacent to the vertices of type ar − m, consider a set A= {a1−m, a2−m, . . . , aφ(n)−m}. Suppose two vertices i and j are adjacent in Gn, then j is of the form ar − i, where ar ∈ Un. Case I: If i is even, then j = ar − i is odd. This implies that f (i) = i and f ( j) = n− j = n− (ar − i). Now, by Theorem 3, we can see that f (i) and f ( j) are adjacent in Xn. It is clear that i 6∈ Un. Now, either j ∈ Un or j 6∈ Un. If j ∈ Un, then by Lemma 2, n− j ∈ Un. Then, by the definition of unitary Cayley sigraph σ2(i j) = +. Now, f (i) 6∈ Un as f (i) is even and f ( j) ∈ Un as f ( j) = n− j ∈ Un. So, by the definition of unitary addition Cayley sigraph σ1( f (i) f ( j)) = +. D. Sinha, A. Dhama, B. Acharya / Eur. J. Pure Appl. Math, 6 (2013), 189-210 196 If j 6∈ Un, then by Lemma 2 n − j 6∈ Un. Then, by the definition of unitary Cayley sigraph σ2(i j) =− and as in the above argument σ1( f (i) f ( j)) = −. Thus, we have σ1( f (i) f ( j)) = σ2(i j). Case II: If i is odd, then j = ar − i is even. Thus, j 6∈ Un. Again, either i ∈ Un or i 6∈ Un. If i ∈ Un, then n− i ∈ Un and σ2(i j) = + and as in the above argument, σ1( f (i) f ( j)) = +. If i 6∈ Un, then n− i 6∈ Un. Hence, by the same argument, σ2(i j) = − and σ1( f (i) f ( j)) = −. Now, one can easily verify that f is one-to-one and onto function that preserves adjacency as well as sign of the edges. Hence, Σn ∼= Sn. 3. Balance in Σn In this section, we establish a characterization of balanced unitary addition Cayley sigraphs. We recall a known result first. Theorem 6 ([43]). The unitary addition Cayley graph Gn, n ≥ 2, is bipartite if and only if either n= 3 or n is even. Lemma 3. For the unitary addition Cayley sigraph Σn = (Σ u n,σ), if n = pa, where p is a prime number, then Σn is an all-positive sigraph. Proof. For the unitary addition Cayley sigraph Σn, if n = pa, then Un consists of all the numbers less than n, which are not multiples of p. Suppose αp and βp are two numbers less than n and multiples of p. Then, by the definition of the unitary addition Cayley sigraph, we have a negative edge only when αp is adjacent to βp. Now, we have three possibilities, viz., αp+ βp < n, αp+ βp = n or αp+ βp > n. When, αp+ βp < n, we see that αp+ βp /∈ Un as it is a number less than n and a multiple of p. Secondly, when αp + βp = n, we get αp+βp = 0 /∈ Un. When αp+βp > n, there exists an integer k such that αp+βp = n+k = k, which is again a number less than n and a multiple of p. This implies αp + βp /∈ Un. Thus, in each case αp is not adjacent with βp since their addition αp + βp /∈ Un. Thus, Σn is an all-positive sigraph. We shall now establish the following characterization of balanced unitary addition Cayley sigraphs. Theorem 7. The unitary addition Cayley sigraph Σn = (Σ u n,σ) is balanced if and only if either n is even or it does not have more than one distinct prime factors. Proof. Necessity: Suppose the unitary addition Cayley sigraph Σn = (Σ u n,σ) is balanced. Assume that the conclusion is false. Suppose n is odd and it has at least two distinct prime factors. So, let n = p a1 1 p a2 2 . . . p am m , where all p1, p2, . . . , pm are distinct primes, p1 6= 2 and D. Sinha, A. Dhama, B. Acharya / Eur. J. Pure Appl. Math, 6 (2013), 189-210 197 p1 < p2 < · · ·< pm. In the unitary addition Cayley graph Σu n, p1 is adjacent with 1 as p1 + 1 is not a multiple of any pi ’s for i = 1,2, . . . , m i.e., p1 + 1 ∈ Un. Now, we claim that p1 and p2 are also adjacent in Σu n. If possible, suppose p1 and p2 are not adjacent in Σu n. This shows, p1 + p2 /∈ Un. Then, p1+ p2 is a multiple of some pi ’s for i = 1,2, . . . , m. Suppose p1+ p2 is a multiple of p1. Then, p1+ p2 = αp1 p2 = αp1− p1 = (α− 1)p1 for some positive integer α, which is not possible. Similarly, we can see that p1 + p2 is not a multiple of p2. Now, the possibilities are i = 3,4, . . . , m. Suppose p1+ p2 = αpi for i = 3,4, . . . , m. Since p1 + p2 is even, α is even and is at least 2, for any positive integer α. But as p1 < p2 < pi , p1 + p2 is always less than any multiple of pi for i = 3,4, . . . , m. Thus, p1 + p2 is not a multiple of any pi ’s for i = 1,2, . . . , m. So p1 + p2 ∈ Un. This shows that p1 and p2 are adjacent in Σu n. Now, if p2 is adjacent with 1 in Σu n, then we have a cycle Z = (p1, p2, 1, p1) in Σn. Clearly, p1 and p2 do not belong to Un and 1 ∈ Un. Then, by the definition of Σn, Z has exactly one negative edge p1p2. Thus, Z is a negative cycle in Σn. This implies that Σn is not balanced. Now, suppose p2 is not adjacent with 1 in Σu n, i.e., p2+ 1 6 inUn. Then, p2+ 1 is multiple of one of the pi ’s for i = 1,2, . . . , m. Clearly, i cannot exceed 1, as p2 < p3 · · · < pm. So, the only possibility is i = 1, whence p2+ 1 is a multiple of p1. Then, p2+ 1= αp1 (1) for some positive integer α. By Lemma 2, it is clear that n − p2 6∈ Un. Now, we claim n − p2 is adjacent with 1 i.e., n− p2+1= n−(p2−1) ∈ Un. If p2−1 ∈ Un, then by Lemma 2, n− p2+1= n−(p2+1) ∈ Un. Suppose p2−1 6∈ Un. Then, p2−1 is a multiple of one of the pi ’s for i = 1,2, . . . , m and by the same argument as above i = 1, whence p2 − 1 is a multiple of p1. Then, p2 − 1 = βp1. But, from equation 1, p2 = αp1− 1. This implies, p2− 1= βp1 αp1− 1− 1= βp1 αp1− 2= βp1 αp1− βp1 = 2 (α− β)p1 = 2. This is not possible as p1 is at least 3. Thus, p2−1 is not a multiple of any of the pi ’s, whence p2 − 1 ∈ Un. Hence, n− p2 + 1 = n− (p2 − 1) ∈ Un, whence n− p2 is adjacent with 1 in Σu n. D. Sinha, A. Dhama, B. Acharya / Eur. J. Pure Appl. Math, 6 (2013), 189-210 198 Now, n− p2 + p1 = n− (p2 − p1). Since p1 < p2 < · · · pm, p2 − p1 is not a multiple of any of the pi ’s for i = 2,3, . . . m. Also, p2 − p1 is not a multiple of p1. This shows that p2 − p1 ∈ Un and by Lemma 2, n− (p2 − p1) ∈ Un. This shows that n− p2 is adjacent with p1 in Σn. Thus, we have a cycle Z ′ = (p1, n− p2, 1, p1) in Σn. Clearly, p1 and n− p2 do not belong to Un and 1 ∈ Un. Then, by the definition of Σn, Z ′ has exactly one negative edge p1(n− p2). Thus, Z ′ is a negative cycle in Σn. This implies that Σn is not balanced, a contradiction to the hypothesis. So, by contraposition, the conditions are satisfied. Sufficiency: Suppose n is even. Then, Un does not contain any multiple of 2. Then, by Theorem 6, Σn is bipartite, whence all its cycles are even. Therefore, every cycle inΣn contains alternately either even-odd or odd-even labeled vertices. Without loss of generality, let Z ′′ = (e1, o1, e2, o2, . . . , em, om, e1) be a cycle of even length in Σn. Clearly, ei /∈ Un∀i = 1,2, . . . , m. Case(i): Suppose o j ∈ Un∀ j = 1,2, . . . , m. Then, all the edges in Z ′′ are positive. Case(ii): Suppose o j /∈ Un for some j = 1,2, . . . , m. Then, Z ′′ contains two negative edges e jo j and o je j+1 with respect to each o j /∈ Un. Thus, Z ′′ contains an even number of negative edges. Since Z ′′ is an arbitrary cycle in Σn, using Lemma 1, we conclude Σn is balanced. Next, suppose n is odd and it does not have more than one distinct prime factors. That means, n = pa. Now, using Lemma 3, Σn is an all-positive sigraph which is trivially balanced. Hence the theorem. 11 0 1 2 3 4 5 6 78 9 10 12 13 14 Figure 3: Smallest unbalanced unitary addition Cayley sigraph D. Sinha, A. Dhama, B. Acharya / Eur. J. Pure Appl. Math, 6 (2013), 189-210 199 The smallest heterogeneous unbalanced unitary addition sigraph is Σ15, which is shown in Figure 3. 4. Clusterability of Σn In this section, we discuss clusterability of unitary addition Cayley sigraphs and obtain the following somewhat surprising result. Theorem 8. A unitary addition Cayley sigraph Σn = (Σ u n,σ) is clusterable if and only if it is balanced. Proof. Sufficiency: Suppose the unitary addition Cayley sigraph Σn = (Σ u n,σ) is balanced. Then, by the definition of clusterability, Σn is clusterable with two clusters. Necessity: Suppose unitary addition Cayley sigraph Σn = (Σ u n,σ) is clusterable. If possible, suppose Σn is not balanced. Then, by Theorem 7, n is odd with at least two distinct prime factors. So, let n = p a1 1 p a2 2 . . . p am m , where all of p1, p2, . . . , pm are distinct primes, p1 6= 2 and p1 < p2 < · · · < pm. Now, as in the proof of Theorem 7, we have at least one of the cycles Z = (p1, p2, 1, p1) and Z ′ = (p1, n− p2, 1, p1) in Σn. Clearly, p1 and p2 do not belong to Un and 1 ∈ Un. Then, by the definition of Σn, Z has exactly one negative edge p1p2. Also, p1 and n− p2 do not belong to Un and 1 ∈ Un. Then, again by the definition of Σn, Z ′ has exactly one negative edge p1(n− p2). Thus, in each case we have a cycle with exactly one negative edge. This shows that Σn is not clusterable, a contradiction to the hypothesis. Thus, Σn is balanced. Hence, the theorem. 5. Sign-compatibility of Σn Theorem 9 ([41]). A sigraph S is sign-compatible if and only if S does not contain a subsigraph isomorphic to either of the two sigraphs, S1 formed by taking the path P4 = (x ,u, v, y) with both the edges xu and v y negative and the edge uv positive and S2 formed by taking S1 and identifying the vertices x and y (Figure 4). x u v y (a) S1 x = y u v (b) S2 Figure 4: Two forbidden subsigraphs for a sign-compatible sigraph [40] D. Sinha, A. Dhama, B. Acharya / Eur. J. Pure Appl. Math, 6 (2013), 189-210 200 Theorem 10. Every unitary addition Cayley sigraph Σn is sign-compatible. Proof. Suppose that the unitary addition Cayley sigraph Σn is not sign-compatible. Then, by Theorem 9, there is at least one positive edge, say vi v j in Σn such that there are negative edges on both the vertices, vi and v j in. Since vi v j is a positive edge in Σn, by the definition of Σn, at least one of vi , v j ∈ Un. As at least one of vi , v j ∈ Un, again by the definition of Σn, there is no negative edge on at least one vertex, a contradiction to the hypothesis. Hence, Σn is sign-compatible. It has been shown elsewhere that all line sigraphs are sign-compatible [5]. Hence, in view of Theorem 10 the question arises whether any unitary addition Cayley sigraph is a line sigraph. The answer of this question is given in Theorem 12. Theorem 11. Unitary addition Cayley graph Gn is a line graph if and only if n ∈ {2,3,4,6}. Proof. Necessity: Suppose unitary addition Cayley graph Gn is a line graph. If possible, suppose n /∈ {2,3,4,6}. Case I: Suppose n is a prime number. Clearly, in this case n≥ 5. Since n is prime, Un contains all numbers from 1 to (n− 1). Now, 0 is adjacent with all the vertices of Gn. Also, for any other vertex i in Gn, i is not adjacent only with (n− i) as i + (n− i) = n = 0 6= Un. Thus, for any two vertices i and j in Gn such that i 6= j 6= 0, we have an induced subgraph in Gn, which is shown in Figure 5. 0 i j n-i n-j Figure 5: Showing an induced subgraph of Gn, which is forbidden for Gn to be a line graph. This is one of the Beineke’s nine forbidden subgraphs for line graph [30]. This shows that Gn is not a line graph, a contradiction to the hypothesis. Case II: Suppose n is not a prime number. Clearly, 1 is (always) adjacent with 0 in Gn. Also, 1 is adjacent with p1, as p1 + 1 ∈ Un, where p1 is the smallest multiple of n. Suppose a is some number such that ap1 = n. Now, 1+ (a− 1)p1 = 1+ ap1− p1 = 1+ n− p1 = n− (p1− 1). D. Sinha, A. Dhama, B. Acharya / Eur. J. Pure Appl. Math, 6 (2013), 189-210 201 Since p1 − 1 ∈ Un, by Lemma 2, n− (p1 − 1) ∈ Un. Thus, 1 and (a− 1)p1 are adjacent in Gn. Also, 0 is not adjacent with p1 and (a−1)p1 as their addition is a multiple of p1. Similarly, p1 and (a− 1)p1 are not adjacent in Gn as their addition is a multiple of p1. Thus, we have an induced subgraph in Gn, which is shown in Figure 6. Again, we have a forbidden subgraph K1,3 for a line graph showing that Gn is not a line graph, a contradiction to the hypothesis. Hence, the condition is satisfied. 0 1 p1 (a-1)p1 Figure 6: Showing K1,3 as an induced subgraph of Gn, which is forbidden for Gn to be a line graph. Sufficiency: Suppose n= 2,3,4 or 6. The corresponding graphs are shown in Figure 7, which are line graphs of P3, P4, C4 and C6, respectively. Hence, the result. 0 1 (a) G2 0 1 2 (b) G3 0 1 23 (c) G4 0 1 2 4 3 5 (d) G6 Figure 7: Showing G2, G3, G4 and G6 Theorem 12. Unitary addition Cayley sigraph Σn is a line sigraph if and only if n ∈ {2,3,4,6}. Proof. Necessity: Suppose the unitary addition Cayley sigraph Σn is a line sigraph. If pos- sible, suppose n /∈ {2,3,4,6}. Then, by Theorem 11, Σu n is not a line graph, a contradiction to the hypothesis. Hence, n ∈ {2,3,4,6}. D. Sinha, A. Dhama, B. Acharya / Eur. J. Pure Appl. Math, 6 (2013), 189-210 202 Sufficiency: Now, suppose n ∈ {2,3,4,6}. The corresponding sigraphs Σ2,Σ3,Σ4 and Σ6 and the sigraphs whose line sigraphs are these sigraphs are shown in Figure 8. Hence, Σn is a line sigraph for n ∈ {2,3,4,6}. 0 1 (a) Σ2 0 1 2 (b) Σ3 0 1 23 (c) Σ4 0 1 2 4 3 5 (d) Σ6 (e) (f) (g) (h) Figure 8: Showing Σ2, Σ3, Σ4 and Σ6 and the sigraphs whose line sigraphs are these sigraphs Remark 1. Unitary addition Cayley sigraph Σn is a product line sigraph if and only if n ∈ {2,3,4,6}. Proof. Suppose the unitary addition Cayley sigraph Σn is a product line sigraph. Since, for any given sigraph S, the underlying graphs of the line sigraph L(S) and the product line sigraph L×(S) are the same, the condition follows from Theorem 11. Conversely, suppose n ∈ {2,3,4,6}. By Theorem 7 for these values of n, Σn is balanced. Since the product line sigraph of any sigraph is always balanced and its underlying structure is the line graph (see [3]), the result follows from Theorem 7 and Theorem 11. Unitary addition Cayley sigraphs Σ2,Σ3,Σ4 and Σ6 and the sigraphs whose product line sigraphs are these sigraph are shown in Figure 9. 6. C -consistency of Σn Now, we present a characterization of C -consistent unitary addition Cayley sigraphs. Theorem 13 ([33]). Let G be a marked graph and T be a spanning tree of G. Then, G is consistent if and only if G satisfies the following two conditions: (i) each fundamental cycle relative to T is positive, and D. Sinha, A. Dhama, B. Acharya / Eur. J. Pure Appl. Math, 6 (2013), 189-210 203 (ii) the two end vertices of any common path between each pair of fundamental cycles relative to T have the same mark. 0 1 (a) Σ2 0 1 2 (b) Σ3 0 1 23 (c) Σ4 0 1 2 4 3 5 (d) Σ6 (e) (f) (g) (h) Figure 9: Showing Σ2, Σ3, Σ4 and Σ6 and the sigraphs whose product line sigraphs are these sigraphs Theorem 14 ([42]). The unitary Cayley sigraph Sn = (S u n,σ), where n has at most two distinct odd prime factors, is C -consistent if and only if n is either odd or n is 2, 6 or a multiple of 4. Lemma 4. In the unitary addition Cayley sigraph Σn, if n = 2p a1 1 , where p1 is an odd prime, then the negative degree of the vertex 2 of Σn is odd. Proof. Suppose n = 2p a1 1 in Σn, where p1 is an odd prime. By the definition of Σn, negative edges are incident at the vertex 2 of Σn only when 2 is adjacent to multiples of p1. Since addition of 2 and any even multiple of p1 is an even number and Un does not contain an even number, the vertex 2 is not adjacent to any even multiple of p1. Now, the number of odd multiples of p1 are p a1−1 1 . Now, 2 is adjacent with all the odd multiples of p1 as their addition with 2 is neither a multiple of 2 nor a multiple of p1. 2 is negatively adjacent with p a1−1 1 . Since p1 is an odd prime, d−(2) is odd. Lemma 5 ([42]). In the unitary Cayley sigraph Sn, if n= 2p a1 1 p a2 2 , where p1 and p2 are distinct odd primes, then the negative degree of the vertex 2 of Sn is odd. Lemma 6. In the unitary addition Cayley sigraph Σn, if n = 2p a1 1 p a2 2 , where p1 and p2 are distinct odd primes, then the negative degree of the vertex 2 of Σn is odd. Proof. Given that n = 2p a1 1 p a2 2 , where p1 and p2 are distinct odd primes, since n is even, Σn ∼= Sn by Theorem 5. Since 2 is an even number, by the consideration of mapping in Theorem 5, vertex 2 of Sn is mapped to the vertex 2 in Σn and by Lemma 5, negative degree of the vertex 2 in Σn is odd. D. Sinha, A. Dhama, B. Acharya / Eur. J. Pure Appl. Math, 6 (2013), 189-210 204 Lemma 7. In the unitary addition Cayley sigraph Σn, if n = p a1 1 p a2 2 , where n is odd, then the negative degree of the vertices of Σn that are multiples of p1 or p2 is even. Proof. Given that n = p a1 1 p a2 2 , where n is odd, and p1 and p2 are distinct odd primes it follows from the definition of Σn, that the negative edges are incident at the vertex p1 when p1 is adjacent to multiples of p2 which do not have p1 as the factor. Every multiple of p2, which does not contain any multiple of p1, is adjacent with p1 as its addition is neither a multiple of p1 nor a multiple of p2. Thus, d−(p1) = p a1 1 p a2−1 2 − p a1−1 1 p a2−1 2 = p a1−1 1 p a2−1 2 (p1− 1). Since p1 and p2 are odd, d−(p1) is even. This formula works for any multiple of p1 except those which have p2 as a factor. Similarly, d−(p2) = p a1−1 1 p a2 2 − p a1−1 1 p a2−1 2 . = p a1−1 1 p a2−1 2 (p2− 1). Since p1 and p2 are odd, d−(p2) is even. This formula works for any multiple of p2 except those which have p1 as a factor. And the negative degree of the vertices of Σn that are multiples of p1p2 is zero. Thus, the negative degree of the vertices of Σn that are multiples of p1 or p2 is even. Theorem 15. The unitary addition Cayley sigraph Σn = (Σ u n,σ), where n has at most two distinct odd prime factors, is C -consistent if and only if n is either odd, or n is 2, 6 or a multiple of 4. Proof. Necessity: Suppose the unitary addition Cayley sigraphΣn = (Σ u n,σ) isC -consistent. Let, on contrary, n ≡ 2 (mod 4) with n 6= 2 and n 6= 6. Then, either n = 2p a1 1 or n = 2p a1 1 p a2 2 , where p1 and p2 are distinct odd primes. Case(i): Suppose n≡ 0 (mod 3). Then, either n= 2×3a1 or n= 2×3a1 × p a2 2 . First, suppose p2 6= 5 and p2 6= 7. Then, due to Lemma 4 and Lemma 6, µσ(2) = −. Since the vertex 5 ∈ Un, by the definition of Σn, d−(5) = 0. It follows, µσ(5) = +. Now, the vertex 5 is adjacent to the vertex 2 since 5+ 2= 7 ∈ Un. Since (n − 4) + (n − 3) = n + (n− 7) = n − 7 ∈ Un as 7 ∈ Un, (n − 4) and (n − 3) are adjacent in Σu n and (n − 3) + 2 = n − 1 ∈ Un. This implies (n − 3) and 2 are also adjacent in Σu n. Similarly, (n−4)+5= n+1= 1 ∈ Un. This implies 5 and (n−4) are adjacent in Σu n. Consider the two cycles, Z1 = (2,5,0,1,4,3,2) and Z2 = (2,5, (n− 4), (n− 3), 2) in Σn. Clearly, the D. Sinha, A. Dhama, B. Acharya / Eur. J. Pure Appl. Math, 6 (2013), 189-210 205 cycles Z1 and Z2 share the chord whose end vertices are 2 and 5. Now, if either Z1 or Z2 is C -inconsistent cycle, then we have a contradiction to the hypothesis. Therefore, Z1 and Z2 are both C -consistent cycles. However, the end vertices 2 and 5 of their common chord are marked oppositely under the canonical marking and this contradicts Theorem 13. Now, if n= 2×3a1 × p a2 2 , where either p2 = 5 or p2 = 7, then since the vertex 11 ∈ Un, by the definition of Σn, d−(11) = 0. It follows, µσ(11) = +. Now, the vertex 11 is adjacent to the vertex 2 since 11+ 2= 13 ∈ Un. Since (n−12)+(n−1) = n+(n−13) ∈ Un as 13 ∈ Un, (n−12) and (n−1) are adjacent in Σu n and (n− 1) + 2 = n+ 1 = 1 ∈ Un. This implies, (n− 1) and 2 are also adjacent in Σu n. Similarly, (n− 12) + 11= n− 1 ∈ Un, which implies 11 and (n− 12) are adjacent in Σu n. Now, consider the two cycles, Z3 = (11,2,9,4,7,6,11) and Z4 = (2,11, (n− 12), (n− 1), 2) in Σn. Clearly, the cycles Z3 and Z4 share the chord whose end vertices are 2 and 11. As argued above, Z3 and Z4 are both C -consistent cycles. However, the end vertices 2 and 11 of their common chord are marked oppositely under the canonical marking, a contradiction to Theorem 13. Case(ii): Suppose either n ≡ 1 (mod 3) or n ≡ 2 (mod 3). That means, 3 does not divide n, which implies that the vertex 3 ∈ Un. Now, consider a cycle Z = (0,1,2, (n− 1), 0) in Σn. Since 1 ∈ Un and (n− 1) ∈ Un, by the definition of Σn, d−(1) = d−(n− 1) = 0. It follows that in the cycle Z , µσ(1) = µσ(n− 1) = +. Since the vertex 0 is adjacent to those vertices which belong to Un, d−(0) = 0. That means, µσ(0) = +. Now, due to Lemma 4 and Lemma 6, µσ(2) = −. Thus, the cycle Z is C -inconsistent, whence Σn is not C -consistent, a contradiction to the hypothesis. Thus, this part of the proof is complete. Sufficiency: Next, suppose n is odd, 2, 6 or a multiple of 4. Case(i): Let n be odd, and n = p a1 1 p a2 2 , where p1 and p2 are distinct odd primes. Using Lemma 7 one can easily see that all the vertices in Σn which are multiples of p1 and p2 are even and all other vertices belong to Un. So, their negative degrees are zero. Hence, all the vertices of Σn are marked positively under the canonical marking. Hence, Σn is C -consistent. Case(ii): Suppose n= 2,6 in Σn. Then, we can easily verify that Σ2 and Σ6 are C -consistent. Case(iii): Suppose n is a multiple of 4. Here n is even and by Theorem 5 Σn ∼= Sn and by Theorem 14, Σn is C−consistent. D. Sinha, A. Dhama, B. Acharya / Eur. J. Pure Appl. Math, 6 (2013), 189-210 206 7. Balance in Certain Derived Sigraphs In this section, we consider the conditions that a given sigraph must satisfy in order that its certain derived sigraphs are balanced. Corollary 1. For the unitary addition Cayley sigraph Σn = (Σ u n,σ), its negation sigraph η(Σn) is balanced if and only if either n= 3 or n is even. Proof. First, suppose η(Σn) is balanced. Assume that the conclusion is false. Suppose n is odd and not equal to 3. Then, 2 ∈ Un. Since 0+ 2 = 2 ∈ Un, 0 and 2 are adjacent in Σu n and 2+ (n− 1) = n+ 1 = 1 ∈ Un. This implies, 2 and n− 1 are adjacent in Σu n. Thus, we can consider a triangle T : (0,2, n−1,0) in Σn. Since 2, n−1 ∈ Un, by the definition of Σn all the edges of T are positive. That means, all the edges of the triangle T are negative in η(Σn). Thus, η(Σn) is unbalanced, which contradicts the hypothesis. Conversely, suppose n is even or n = 3. Now, due to Theorem 6, Su n is bipartite and due to Theorem 7, Σn is balanced. Thus, η(Σn) is balanced. Theorem 16 ([4]). For a sigraph S, its line sigraph L(S) is balanced if and only if the following conditions hold: (i) for any cycle Z in S, (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, and (ii) for v ∈ S, if d(v)> 2, then there is at most one negative edge incident at v in S. Corollary 2. For the unitary addition Cayley sigraph Σn, its line sigraph L(Σn) is balanced if and only if n= pa, where p is a prime number. Proof. Suppose L(Σn) is balanced for the unitary addition Cayley sigraph Σn. Assume that the conclusion is false. Let n have at least two distinct prime factors. Suppose p1 and p2 are two smallest prime factors of n such that p1 < p2. It is shown in the proof of Theorem 7, p1 is adjacent with 1 and p2. Suppose αp2 = n for any positive integer α. Now, (α− 1)p2+ p1 = αp2− p2+ p1 = n− p2+ p1 = n− (p2− p1) Since p2− p1 ∈ Un, by Lemma 2 n− (p2− p1) ∈ Un, whence (α− 1)p2+ p1 ∈ Un. This shows that (α− 1)p2 is adjacent with p1. Clearly, the vertex p2 and (α− 1)p2 are adjacent to the vertex p1 with negative edges in Σn. That means, d−(p1) ≥ 2 and clearly d(p1) > 2 except n = 6 in Σn. Thus, condition (ii) of Theorem 16 does not hold for Σn and when n = 6 it is easy to see that condition (i)(b) does not hold, which implies that L(Σn) is unbalanced, a contradiction to the hypothesis. Hence n= pa, where p is a prime number. Converse part can be proved easily by using Lemma 3. D. Sinha, A. Dhama, B. Acharya / Eur. J. Pure Appl. Math, 6 (2013), 189-210 207 Theorem 17 ([6]). For any sigraph S, CE(S) is balanced if and only if S is a balanced sigraph such that for every vertex v ∈ V (S) 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 (iii) for every x-y path P4 = (x , v, w, y) of length three, vw is a positive edge in S. Theorem 18. For the unitary addition Cayley sigraph Σn = (Σ u n,σ), its CE(Σn) is balanced if and only if n= pa or n= 6, where p is a prime number. Proof. Suppose CE(Σn) is balanced for the unitary addition Cayley sigraph Σn. Assume that the conclusion is false. Let n 6= 6 and have at least two distinct prime factors. So, let n= p a1 1 p a2 2 . . . p am m , where all of p1, p2, . . . , pm are distinct primes and p1 < p2 < · · ·< pm. Case I: Suppose n is even. Clearly, p1 = 2 /∈ Un. p2 can never be adjacent with any number in Un because Un contains only odd numbers as n is even and then sum of these two ele- ments will be always even and does not belong to Un. Since p2 /∈ Un, by Theorem 4, we have d(p2) = φ(n). So all the degrees of p2 are negative and greater than 3. Thus, the condition (i) of Theorem 17 does not hold for Σn, which implies that CE(Σ) is unbalanced, a contradiction to the hypothesis. Case II: Now, suppose n is odd. We have already shown that p1 is adjacent p2. Clearly, d(p1) > 3 and d−(p1) ≥ 1. Thus, condition (i) of Theorem 17 does not hold for Σn, which implies that CE(Σ) is unbalanced, a contradiction to the hypothesis. Hence n = pa or n = 6, where p is a prime number. Converse part can be proved easily by using Lemma 3. Theorem 19 ([3]). The ×-line sigraph L×(S) of a sigraph S is a balanced sigraph. Theorem 20. For the unitary addition Cayley sigraph Σn, its ×-line sigraph L×(Σn) is balanced. Proof. Result follows from Theorem 19. Theorem 21 ([44]). The semi-total line sigraph T1(S) of a sigraph S is a balanced sigraph. Theorem 22. For the unitary addition Cayley sigraph Σn, its semi-total line sigraph T1(Σn) is balanced. Proof. Result follows from Theorem 21. ACKNOWLEDGEMENTS This research is supported by the Department of Science and Tech- nology (Govt. of India), New Delhi, India under the Project SR/S4/MS: 409/06. REFERENCES 208 References [1] B.D. Acharya, A spectral criterion for cycle balance in networks, Journal of Graph Theory, 4(1), 1-11. 1980. [2] B.D. Acharya, A characterization of consistent marked graphs, National Academy of Sci- ence Letters, 6, 431-440. 1983 [3] M. Acharya,×-line sigraph of a sigraph, Journal of Combinatorial Mathematics and Com- binatorial Computing, 69, 103-111. 2009. [4] M. Acharya and D. Sinha, A characterization of sigraphs whose line sigraphs and jump sigraphs are switching equivalent, Graph Theory Notes N. Y., XLIV, 30-34. 2003. [5] M. Acharya and D. Sinha, Characterizations of line sigraphs, National Academy of Science Letters, 28(1 & 2), 31-34. 2005. [6] M. Acharya and D. Sinha, Common-edge sigraphs, AKCE International Journal of Graphs and Combinatorics, 3(2), 115-130. 2006. [7] R. Akhtar, M. Boggess, T. Jackson-Henderson, I. Jiménez, R. Karpman, A. Kinzel and D. Pritikin, On the unitary Cayley graph of a finite ring, Electronic Journal of Combinatorics, 16(1)(2009), #R117. [8] N. Alon, Large sets in finite fields are sumsets, Journal of Number Theory, 126(1)(2007), 110-118. [9] N.D. Beaudrap, On restricted unitary Cayley graphs and symplectic transformations mod- ulo n, Electronic Journal of Combinatorics, 17(2010), #R69. [10] M. Behzad and G.T. Chartrand, Line coloring of signed graphs, Elemente der Mathematik, 24(3) (1969), 49-52. [11] L.W. Beineke and F. Harary, Consistency in marked graphs, Journal of Mathematical Psy- chology, 18(3)(1978), 260-269. [12] L.W. Beineke and F. Harary, Consistent graphs with signed points, Rivista di Matematica per le Scienze Economiche e Sociali, 1(1978), 81-88. [13] P. Berrizbeitia and R.E. Giudici, On cycles in the sequence of unitary Cayley graphs, Dis- crete Mathematics, 282(1-3)(2004), 239-243. [14] N. Biggs, Algebraic Graph Theory, Second Edition, Cambridge Mathematical Library, Cambridge University Press, 1993. [15] M. Boggess, T. Jackson-Henderson, I. Jiménez and R. Karpman, The structure of unitary Cayley graphs, SUMSRI Journal, (2008), 1-23. REFERENCES 209 [16] G.T. Chartrand, Graphs as Mathematical Models, Prindle, Weber and Schmidt. Inc., Boston, Massachusetts, 1977. [17] B. Cheyne, V. Gupta and C. Wheeler, Hamilton cycles in addition graphs, Rose-Hulman Undergraduate Math Journal, 4(1)(2003), 1-17. [18] F.R.K. Chung, Diameters and eigenvalues, Journal of the American Mathematical Society, 2(2)(1989), 187-196. [19] J.A. Davis, Clustering and structural balance in graphs, Human Relations, 20(1967), 181- 187. [20] I.J. Dejter and R.E. Giudici, On unitary Cayley graphs, Journal of Combinatorial Mathe- matics and Combinatorial Computing, 18(1995), 121-124. [21] A. Droll, A classification of Ramanujan unitary Cayley graphs, Electronic Journal of Com- binatorics, 17(2010), #N29. [22] E.D. Fuchs and J. Sinz, Longest induced cycles in Cayley graphs, eprint arXiv:math/0410308v2 (2004), 1-16. [23] E.D. Fuchs, Longest induced cycles in circulant graphs, Electronic Journal of Combina- torics, 12(2005), 1-12. [24] M.K. Gill, Contribution to some topics in graph theory and its applications, Ph.D. Thesis, Indian Institute of Technology, Bombay, 1983. [25] C. Godsil and G. Royle, Algebraic Graph Theory, Graduate Texts in Mathematics, Springer, 207, 2001. [26] B.J. Green, Counting sets with small sumset, and the clique number of random Cayley graphs, Combinatorica, 25(2005), 307-326. [27] D. Grynkiewicz, V.F. Lev and O. Serra, The connectivity of addition Cayley graphs, Elec- tronic Notes in Discrete Mathematics, 29(2007), 135-139. [28] D. Grynkiewicz, V.F. Lev and O. Serra, Connectivity of addition Cayley graphs, Journal of Combinatorial Theory, Series B, 99(1)(2009), 202-217. [29] F. Harary, On the notion of balance of a signed graph, Michigan Mathematical Journal, 2(1953), 143-146. [30] F. Harary, Graph Theory, Addison-Wesley Publishing Company, Reading, Massachusetts, 1969. [31] F. Harary and J.A. Kabell, A simple algorithm to detect balance in signed graphs, Mathe- matical Social Sciences, 1(1980-81), 131-136. REFERENCES 210 [32] F. Harary and J.A. Kabell, Counting balanced signed graphs using marked graphs, Pro- ceedings of the Edinburgh Mathematical Society, 24(2)(1981), 99-104. [33] C. Hoede, A characterization of consistent marked graphs, Journal of Graph Theory, 16(1)(1992), 17-23. [34] W. Klotz and T. Sander, Some properties of unitary Cayley graphs, Electronic Journal of Combinatorics, 14(2007), #R45. [35] V.F. Lev, Sums and differences along Hamiltonian cycles, Electronic Notes in Discrete Math- ematics, 28(2007), 25-31. [36] V.F. Lev, Sums and differences along Hamiltonian cycles, Discrete Mathematics, 310(3)(2010), 575-584. [37] H.N. Ramaswamy and C.R. Veena, On the energy of unitary Cayley graphs, Electronic Journal of Combinatorics, 16(2009), #N24. [38] E. Sampathkumar and S.B. Chikkodimath, Semitotal graphs of a graph-I, Journal of Kar- natak University Science, 18(1973), 274-280. [39] T. Sander, Eigenspaces of Hamming graphs and unitary Cayley graphs, Ars Mathematica Contemporanea, 3(2010), 13-19. [40] D. Sinha, New frontiers in the theory of signed graphs, Ph.D. Thesis, University of Delhi, 2005. [41] D. Sinha and A. Dhama, Sign-Compatibility of some derived signed graphs, Indian Journal of Mathematics, 55(1), 2013. [42] D. Sinha and P. Garg, On the unitary Cayley signed graphs, Electronic Journal of Combi- natorics, 18(2011), #P229. [43] D. Sinha, P. Garg and A. Singh, Some properties of unitary addition Cayley graphs, Notes on Number Theory and Discrete Mathematics, 17(3)(2011), 49-59. [44] D. Sinha and P. Garg, Some results on semi-total signed graphs, Discussiones Mathemati- cae. Graph Theory, 31(4)(2011b), 625-638. [45] D.B. West, Introduction to Graph Theory, Prentice-Hall of India Pvt. Ltd., 1996. [46] T. Zaslavsky, Glossary of signed and gain graphs and allied areas, II Edition, Electronic Journal of Combinatorics, #DS8(1998). [47] T. Zaslavsky, A mathematical bibliography of signed and gain graphs and allied areas, VII Edition, Electronic Journal of Combinatorics, #DS8(1998). (Latest update: 8th Edition, September 2012). [48] T. Zaslavsky, Signed analogs of bipartite graphs, Discrete Mathematics, 179(1998), 205- 216, (1998).