/compile/output.dvi EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 8, No. 4, 2015, 469-477 ISSN 1307-5543 – www.ejpam.com ! -cycle Compatible Splitting Signed Graphs S(S) and !(S) Rashmi Jain 1,", Sangita Kansal1, Mukti Acharya2 1 Department of Applied Mathematics, Delhi Technological University, Delhi, India 2 Department of Mathematics, Kalasalingam University, KrishnanKoil, India Abstract. A signed graph (or, in short, sigraph) S = (Su,!) consists of an underlying graph Su := G = (V, E) and a function ! : E(Su) #$ {+,#}, called the signature of S. A marking of S is a function µ : V (S) #$ {+,#}. The canonical marking of a signed graph S, denoted µ!, is given as µ!(v) := ! vw%E(S) !(vw). The splitting signed graph S(S) of a signed graph S is formed as follows: • Take a copy of S and for each vertex v of S, take a new vertex v&. Join v& to all vertices u % N(v) by negative edge, if µ!(u) = µ!(v) = # in S and by positive edge otherwise. The splitting signed graph !(S) of a signed graph S is formed as follows: • Take a copy of S and for each vertex v of S, take a new vertex v&. Join v& to all vertices u % N(v) and assign !(uv) as its sign. Here, N(v) is the set of all adjacent vertices to v. A signed graph is called canonically consistent (or ! -consistent) if its every cycle contains even number of negative vertices with respect to its canonical marking. A marked signed graph S is called cycle- compatible if for every cycle Z in S, the product of signs of its vertices equals the product of signs of its edges. A signed graph S is ! -cycle compatible if for every cycle Z in S, ! e%E(Z) !(e) = ! v%V (Z) µ!(v). In this paper, we establish a structural characterization of signed graph S for which S(S) and !(S) are isomorphic and ! -cycle compatible. 2010 Mathematics Subject Classifications: 05C22; 05C75 Key Words and Phrases: canonical marking, splitting signed graph, ! -consistent, ! -cycle compatible, ! -sign compatible "Corresponding author. Email addresses: rashmi2011f@gmail.com (R. Jain), sangita_kansal15@dce.ac.in (S. Kansal), mukti1948@gmail.com (M. Acharya) http://www.ejpam.com 469 c' 2015 EJPAM All rights reserved. R. Jain, S. Kansal, M. Acharya / Eur. J. Pure Appl. Math, 8 (2015), 469-477 470 1. Introduction A graph is an ordered pair G = (V, E), where V = V (G) is a set of vertices or points of G and E = E(G) is a collection of pairs of vertices of G, called edges or lines of G. For graph theoretical terminology, we refer to [2]. All graphs considered in the paper are finite, simple and connected. A signed graph is an ordered pair S = (Su,!), where Su := G = (V, E) is a graph called the underlying graph of S and ! : E(Su) #$ {+,#} is a function, called the signature of S. In other terms, we say that the edges are signed by !. In a pictorial representation of a signed graph S, its positive edges are shown as bold line segments (‘Jorden curves’ drawn on the plane) and negative lines as broken line segments as shown in Figure 1. E + (S) = {e % E(Su) : !(e) = +} and E – (S) = {e % E(Su) : !(e) = #}. The elements of E + (S) (E – (S)) are called positive (negative) edges of S and the set E(S) = E + (S)( E – (S) is called the edge set of S. S: (S):1 2 3 4 1 2 3 4 1' 2' 3' 4' 1 2 3 4 1' 2' 3' 4' (S): (S): Figure 1: A signed graph S and its splitting signed graphs S(S) and !(S) A signed graph in which all the edges are positive, is called all-positive signed graph (all- negative signed graph is defined similarly). A signed graph is said to be homogeneous if it is either all-positive or all-negative and heterogeneous otherwise. By d(v), we denote degree of v % V (S), d(v) = d+(v)+ d#(v), here d+(v) (d#(v)) denotes the positive (negative) degree of v. A marking of S is a function µ : V (S) #$ {+,#}. Sampathkumar in [4] introduced the idea of marking derived from the signs of edges incident to vertices, given as µ!(v) := ! vw%E(S) !(vw). This marking is called canonical marking. Clearly, µ!(v) = + if d#(v) is even and µ!(v) = # if d#(v) is odd. Thus, in canonical marking of a signed graph, we assign + sign to a vertex if its negative degree is even and - sign if its negative degree is odd. In this paper, a vertex v of d#(v) = even (odd) is called positive (negative) vertex. R. Jain, S. Kansal, M. Acharya / Eur. J. Pure Appl. Math, 8 (2015), 469-477 471 Signed graphs S1 and S2 are called isomorphic, written as S1 )= S2, if there is a graph isomorphism f : Su 1 $ Su 2 that preserves edge signs. A cycle in a signed graph is said to be positive (negative) cycle if the product of the signs of its edges is positive (negative), i.e., its an even (odd) number of edges are negative. A signed graph is said to be balanced if every cycle in it is positive (see [3]). A cycle in a marked signed graph is said to be consistent if its an even number of vertices are negative and a marked signed graph is called consistent if its all cycles are consistent (see [6]). Similarly, a cycle in a signed graph is said to be canonically consistent (or ! -consistent) if for every cycle in S, the product of signs of its vertices with respect to canonical marking, is positive, i.e., its an even number of vertices are negative and a signed graph is called ! - consistent if its all cycles are ! -consistent. A marked signed graph S is called cycle-compatible if for every cycle Z in S, the product of signs of its vertices equals the product of signs of its edges. A signed graph S is called canonically cycle (or ! -cycle) compatible if for every cycle Z in S, ! e%E(Z) !(e) = ! v%V (Z) µ!(v). A signed graph S = (Su,!) is said to be sign-compatible [6] if it has a vertex marking µ such that every edge e = uv has !(e) = # if and only if µ(u) = µ(v) = #. If the canonical marking µ! has this property, then S is said to be canonically sign-compatible (or ! -sign-compatible). 2. Splitting Signed Graphs Sampathkumar and Walikar introduced the concept of splitting graph of a graph in [5]. The splitting graph of a graph G, denoted here S(G), is formed as follows: Take a copy of G and for each vertex v of G, take a new vertex v&. Join v& to all adjacent vertices of v. There are two notions of splitting signed graphs of a signed graph S = (Su,!) in the liter- ature, viz., S(S) and !(S), both of which have S(Su) as their underlying graph; only the rule to assign signs to the edges of S(Su) differ. An edge uv& in S(S) is negative whenever u and v are negative vertices of S and an edge uv& in !(S) is negative whenever uv is a negative edge of S as reported in [1] and [7] respectively. A signed graph S is called a S-splitting (!-splitting) signed graph if there exists a signed graph T such that S is isomorphic to S(T ) (!(T )). Theorem 1 (Acharya et al.[1]). Following statements hold: (i) If v % V (S) is a positive vertex then v, v& % V (S(S)) are positive. (ii) If v % V (S) is a negative vertex having an even (odd) number of negative vertices in its neighbourhood then v % V (S(S)) is negative (positive) vertex and v& is of opposite sign to v. Here v& is the vertex as defined above. R. Jain, S. Kansal, M. Acharya / Eur. J. Pure Appl. Math, 8 (2015), 469-477 472 Theorem 2 (Acharya et al. [1]). S(S) is balanced if and only if the following conditions hold in S: (i) S is balanced and; (ii) S does not contain a homogeneous path P3 of marking +, -, - and the marking of a hetero- geneous path P3 is +, -, - only. Lemma 1 (Sinha et al. [7]). The following statements hold in !(S): (i) If v % V (S) is any vertex then v % V (!(S)) is positive. (ii) If v % V (S) is a negative vertex then v& % V (!(S)) is negative. Theorem 3 (Sinha et al. [7]). The splitting signed graph !(S) of a signed graph S is balanced if and only if S is balanced. Figure 1 illustrates a signed graph S and its splitting signed graphs S(S) and !(S). 3. Main Results Theorem 4. For a signed graph S, S(S))= !(S) if and only if S is any one of the following: (i) All-positive or; (ii) All-negative in which degree of each vertex is odd or; (iii) Heterogeneous in which end vertices of every negative (positive) edge are (are not) negative. Proof. Necessity: Let, for a signed graph S, S(S) )= !(S). Since S is a subsignedgraph of S(S) and !(S), we concentrate our attention only on the sign of edge uv& in S(S) and !(S). By the definition of S(S), uv& % E#(S(S)) if and only if u, v % V (S) are negative and by the definition of !(S), uv& % E#(!(S)) if and only if uv % E#(S). Therefore, we have following three possible cases: Case I: If S(S) )= !(S) and both S(S) and !(S) are all-positive then no edge of S will be negative. Hence, (i) follows. Case II: If S(S))= !(S) and both are all-negative then every edge and every vertex of S will be negative. Hence, (ii) follows. Case III: If S(S))= !(S) and both are heterogeneous then S will be heterogeneous and edge uv& in both S(S) and !(S) must be of the same sign. This implies that end vertices of every negative (positive) edge of S are (are not) negative. Hence, (iii) follows. Thus, the necessity follows. Sufficiency: Suppose S is any one of the following: (i) All-positive or; R. Jain, S. Kansal, M. Acharya / Eur. J. Pure Appl. Math, 8 (2015), 469-477 473 (ii) All-negative in which degree of each vertex is odd or; (iii) Heterogeneous in which end vertices of every negative (positive) edge are (are not) negative. then by the definitions S - and !- splitting signed graphs, we obtain following results: Case I: If S is all-positive then S(S) and !(S) will be all-positive and S(S))= !(S). Case II: If S is all-negative in which degree of each vertex is odd then S(S) and !(S) will be all-negative and S(S))= !(S). Case III: If S is heterogeneous in which end vertices of every negative (positive) edge are (are not) negative then S(S) and !(S) will be heterogeneous as S be a subsignedgraph of S(S) and !(S) and edge uv& in both S(S) and !(S) will be of the same sign. Hence, S(S))= !(S). This completes the proof. Corollary 1. For a signed graph S, S(S))= !(S) if and only if S is ! -sign compatible. Theorem 5. S(S) is ! -cycle compatible if and only if the following conditions hold in S: (i) if Z is a positive (negative) cycle then an even (odd) number of negative vertices of cycle Z contain even numbers of negative vertices in their neighbourhoods and; (ii) for a path P3 = (u, v, w), any one condition holds: • it is homogeneous of marking +, +, +; • it is heterogeneous of marking +, -, +; • it is homogeneous (heterogeneous) of marking -, +, + or -, -, + and N(u) contains an odd (even) number of negative vertices; • it is homogeneous (heterogeneous) of marking -, +, - and vertices u, w are (are not) of same parity (i.e., N(u) and N(w) contain even number of negative vertices or odd number of negative vertices); • it is homogeneous (heterogeneous) of marking -, -, - and vertices u, w are not (are) of the same parity. Proof. Necessity: Let S(S) be ! -cycle compatible. Therefore, every cycle in S(S) is either positive and! -consistent or negative and! -inconsistent. By Theorem 1, every positive vertex of S is positive in S(S) and every negative vertex of S having an even (odd) number of negative vertices in its neighbourhood is negative (positive) in S(S). Since S is subsignedgraph of S(S), if Z is a positive (negative) cycle of S then Z must be ! -consistent (! -inconsistent) in S(S), i.e., an even (odd) number of negative vertices of cycle Z must contain an even numbers of negative vertices in their neighbourhoods. Thus, (i) follows. By the definition of S(S), a path P3 = (u, v, w) of S induces a cycle C4 = (u, v, w, v&) in S(S). The marking of path P3 = (u, v, w) may be one of the following: R. Jain, S. Kansal, M. Acharya / Eur. J. Pure Appl. Math, 8 (2015), 469-477 474 1. +, +, + 2. +, -, + 3. -, +, + 4. -, -, + 5. -, +, - 6. -, -, - Hence, the following cases arise: • if marking of path P3 = (u, v, w) is +, +, + then by Theorem 1, vertices u, v, w, v& have signs +, +, +, + respectively in S(S). Thus, path P3 induces a ! -consistent cycle C4 in S(S). By Theorem 2, this cycle C4 is positive (negative) if and only if P3 is homogeneous (heterogeneous). Since S(S) is ! -cycle compatible, P3 will be homogeneous. • if marking of path P3 = (u, v, w) is +, -, + then by Theorem 1, vertices u, v, w, v& have signs+, -, +, + or+, +, +, - respectively in S(S). Thus, path P3 induces a! -inconsistent cycle C4 in S(S). By Theorem 2, this cycle C4 is positive (negative) if and only if P3 is homogeneous (heterogeneous). Since S(S) is ! -cycle compatible, P3 will be heteroge- neous. • if marking of path P3 = (u, v, w) is -, +, + and N(u) contains an odd (even) number of negative vertices then by Theorem 1, vertices u, v, w, v& have signs +, +, +, + (-, +, +, +) respectively in S(S). Thus, path P3 induces a ! -consistent (! -inconsistent) cycle C4 in S(S). By Theorem 2, this cycle C4 is positive (negative) if and only if P3 is homogeneous (heterogeneous). Since S(S) is ! -cycle compatible, for homogeneous (heterogeneous) P3, N(u) must contain an odd (even) number of negative vertices. Similarly, if marking of path P3 = (u, v, w) is -, -,+ and N(u) contains an even (odd) num- ber of negative vertices then by Theorem 1, vertices u, v, w, v& have signs -, -, +, + or -, +, +, - (+, -, +, + or +, +, +, -) respectively in S(S). Thus, path P3 induces a ! -consistent (! -inconsistent) cycle C4 in S(S). By Theorem 2, this cycle C4 is positive (negative) if and only if P3 is heterogeneous (homogeneous). Since S(S) is ! -cycle compatible, for heterogeneous (homogeneous) P3, N(u) will contain an even (odd) number of negative vertices. • if marking of path P3 = (u, v, w) is -, +, - and vertices u and w are (are not) of the same parity, i.e., N(u) and N(w) contain even number of negative vertices or odd number of negative vertices, then by Theorem 1, vertices u, v, w, v& have signs -, +, -, + or +, +, +, + (-, +, +, + or +, +, -, +) respectively in S(S). Thus, path P3 induces a ! -consistent (! -inconsistent) cycle C4 in S(S). By Theorem 2, this cycle C4 is positive (negative) if and only if P3 is homogeneous (heterogeneous). Since S(S) is ! -cycle compatible, for homogeneous (heterogeneous) P3, vertices u and w will (will not) be of the same parity; • if marking of path P3 = (u, v, w) is -, -, - and vertices u and w are (are not) of the same parity, i.e., N(u) and N(w) contain even number of negative vertices or odd number of negative vertices, then by Theorem 1, vertices u, v, w, v& have signs -, -, -, +; -, +, -, - or +, -, +, +; +, +, +, - (-, -, +, +; -, +, +, - or +, -, -, +; +, +, -, -) respectively in S(S). Thus, path P3 induces a ! -inconsistent (! -consistent) cycle C4 in S(S). By Theorem 2, this cycle C4 is positive (negative) if and only if P3 is homogeneous (heterogeneous). Since S(S) is ! -cycle compatible, for homogeneous (heterogeneous) P3, vertices u and w will not (will) be of the same parity. R. Jain, S. Kansal, M. Acharya / Eur. J. Pure Appl. Math, 8 (2015), 469-477 475 Thus, the necessity follows. Sufficiency: A cycle in S(S) is induced due to a cycle or a path P3 or their combinations in S. If conditions hold then it can be easily seen that every cycle in S(S) is positive and ! -consistent or negative and ! -inconsistent, i.e, S(S) is ! -cycle compatible. This completes the proof. Signed graph S shown in Figure 2 does not satisfy conditions (i) and (ii) of Theorem 5, S(S) is ! -cycle incompatible. 3 10 S: 6 7 8 2 1 4 9 3 10 5 6 7 8 2 1 4 9 3 10 6 7 8 2 1 9 3 10 5 6 7 8 2 1 4 9 1' 22 2' 3' 4' 5' 6' 7' 8' 9' 10' (S): Figure 2: A signed graph S and its ! -cycle incompatible S(S) Signed graph S shown in Figure 3 satisfies conditions (i) and (ii) of Theorem 5, S(S) is ! -cycle compatible. S: (S): 3 4 5 1' 2' 3' 4' 2 1 32 1 3 2 1 5' 4 5 Figure 3: A signed graph S and its ! -cycle compatible S(S) Theorem 6. For a signed graph S, !(S) is ! -cycle compatible if and only if the following condi- tions hold in S: (i) S is balanced; (ii) each non-pendant vertex of S is positive. Proof. Necessity: Let !(S) be ! -cycle-compatible, i.e., every cycle in !(S) is either positive and ! -consistent or negative and ! -inconsistent. By Lemma 1, every vertex of S is a positive vertex of !(S). Hence, every cycle Z of !(S) that is due to a cycle Z of S is ! -consistent. Since !(S) is ! -cycle-compatible, this cycle Z of S must be positive. Therefore, S will be balanced. Thus, (i) follows. REFERENCES 476 By the definition of !(S), a path P3 = (u, v, w) of S induces a positive cycle C4 = (u, v, w, v&) in !(S) and by Lemma 1, vertices u, v, w, v& have signs +, +, +, + or +, +, +, - in !(S) if v is a positive (negative) vertex of S. Thus, this cycle C4 is ! -consistent if v % V (S) is a positive vertex. Since !(S) is ! -cycle compatible and cycle C4 is positive, C4 must be ! -consistent. Hence, every non-pendant vertex of S will be positive. Thus, the necessity follows. Sufficiency: A cycle in !(S) is induced due to a cycle or a path P3 or their combinations in S. If conditions hold then it can be easily seen that every cycle in !(S) is positive and ! -consistent, i.e, !(S) is ! -cycle-compatible. This completes the proof. Signed graph S shown in Figure 4 satisfies conditions (i) and (ii) of Theorem 6, !(S) is ! -cycle compatible. 2 3 S: 1 2' 1' 3' 4' 4 5 5' 7 2 1 4 7' 7 6 2 3 1 4 7 6 5 6' (S): Figure 4: A signed graph S and its ! -cycle compatible !(S) ACKNOWLEDGEMENTS The authors are thankful to Dr B. D. Acharya who always nurtured but could not witness the same. The corresponding author is thankful to the University Grants Commission (UGC), Govt. of India, for granting her research fellowship. References [1] M. Acharya, R. Jain, and S. Kansal. Some results on the splitting signed graphs S(S), Journal of Combinatorics, Information and System Sciences, 39(1-2), 23-32. 2014. [2] F. Harary. Graph Theory, Addison-Wesley Publishing Co., Reading, Massachusetts, 1969. [3] F. Harary. On the notion of balance of a signed graph, Michigan Mathematical Journal, 2, 143-146. 1953. [4] E. Sampathkumar. Point-signed and line-signed graphs, National Academy Science Letters, 7(3), 91-93. 1984. [5] E. Sampathkumar and H.B. Walikar. On the splitting graph of a graph, Karnatak University Journal of Sciences, XXV-XXVI, 13-16. 1980-1981. [6] D. Sinha. New frontiers in the theory of signed graphs, Ph.D. Thesis, University of Delhi, India, 2005. REFERENCES 477 [7] D. Sinha, P. Garg, and H. Saraswat. On the splitting signed graphs, Journal of Combina- torics, Information and System Sciences, 38(1-4), 103-111. 2013.