Negation switching invariant signed graphs

Deepa Sinha^a , Ayushi Dhama^b

^aSouth Asian University, Akbar Bhawan, Chankyapuri, New Delhi-110 021.

^bCentre for Mathematical Sciences, Banasthali University, Banasthali-304 022 Rajasthan, India.

deepa−sinha2001@yahoo.com, ayushi.dhama2@gmail.com

A signed graph (or, sigraph in short) is a graph G in which each edge x carries a value σ(x) ∈ {−, +} called its sign. Given a sigraph S, the negation η(S) of the sigraph S is a sigraph obtained from S by reversing the sign of every edge of S. Two sigraphs S¹ and S² on the same underlying graph are switching equivalent if it is possible to assign signs '+' ('plus') or '−' ('minus') to vertices of S¹ such that by reversing the sign of each of its edges that has received opposite signs at its ends, one obtains S2. In this paper, we characterize sigraphs which are negation switching invariant and also see for what sigraphs, S and η(S) are signed isomorphic.

Keywords: Balanced sigraph, Marked sigraph, Signed isomorphism, Switching equivalence Mathematics Subject Classification : Primary 05C 22; Secondary 05C 75.

1. Introduction

For standard terminology and notation in graph theory we refer to West (1996) and Zaslavsky (1998) for sigraphs. Throughout the paper, we consider finite, undirected graphs with no loops or multiple edges.

Formally, a signed graph (or, sigraph in short) is an ordered pair S = (S u , σ), where S ^u = (V, E) is a graph called the underlying graph of S and σ : E → {+, −} is a func-

Received: 16 August 2013, Revised: 5 January 2014, Accepted: 25 January 2014.

tion from the edge set E of S u into the set {+, −}, called the signature (or sign in short) of S. Alternatively, the sigraph can be written as S = (V, E, σ), with V , E and σ in the above sense. Further, E ⁺(S) will denote the set of all the edges of S u that are mapped by σ to the element + and E ⁻(S) = E(S) − E ⁺(S). The elements of E ⁺(S) are called positive edges and those of E ⁻(S) are called negative edges of S. We may then regard any graph as a sigraph in which every edge is positive. In general, a subsigraph S ⁰ of S is said to be all positive (all negative) if all the edges in S 0 are positive (negative). A subsigraph of S is said to be homogeneous if it is either all-positive or all-negative and heterogeneous otherwise. In a pictorial representation of a sigraph S, its positive edges are shown as bold line segments and negative edges as broken line segments. An example of such discrete structures is exhibited in Figure 1, where solid line segments represent edges that are assigned '+' and broken line segments represent those that are assigned '−'. Thus, in a pictorial representation of a graph, one would see only unbroken line segments alone, as every edge of a graph may be assumed to have been designated to be positive. By an independent positive (negative) edge of S we mean a positive (negative) edge of S at each end of which no other positive (negative) edge of S is incident. The negation η(S) of the sigraph S is a sigraph obtained from S by reversing the sign of every edge of S. A sigraph S and its negation η(S) are shown in Figure 1.

Figure 1. A sigraph and its negation

Sigraphs were introduced by Harary (1953) as prototype models to represent structures of cognitive inter relations between two individuals in a social group. Ever since, sigraphs have received much attention in social psychology because of their extensive use in modeling a verity of cognitive-based social processes (e.g., see Abelson and Rosenberg, 1958; Harary, 1953,1957; Katai and Iwai, 1978a, 1978b; Fiksel, 1980; Acharya and Joshi, 2003; Kovchegov, 1994). Further intensive study of the topic has been due to their subsequently discovered connections with classical mathematical systems (e.g., Zaslavsky, 1998; Singh, 2004; Acharya and Singh, 2004, 2005) used in solving a verity of problems of theoretical and practical interest.

Here hVii determines the induced subsigraph of S on the vertex subset Vⁱ of V (S) whereas hVii ^u determines the underlying subgraph of S ^u which is induced by the vertex subset Vⁱ of V (S u ). Subsigraphs may also be induced by sets of edges. If S 0 is the set of edges, the edge-induced subsigraph hS 0 i is the subsigraph of S whose edge set is S 0 and whose vertex set consists of all ends of edges of S 0 .

Two sigraphs \(S_1\) and \(S_2\) are signed isomorphic (written \(S_1 \cong S_2\) or sometimes \(S_1 = S_2\)) if there exists an one-to-one correspondence between their vertex sets which preserve adjacency as well as sign.

Any function \(\mu:V(S)\longrightarrow \{-,+\}\) is called a marking of the sigraph S and \(S_\mu\) is then called the marked sigraph. Switching a sigraph S with respect to the given marking \(\mu\) means to obtain another sigraph \(S=\mathbf{S}_\mu(S)\) from \(S_\mu\) by changing the sign of each of its edge x=uv for which \(\mu(u)=-\mu(v)\) (as shown in Figure 2). The resulting sigraph \(\mathbf{S}_\mu(S)\) is called switched sigraph. A sigraph S switches to another sigraph S' written \(S\sim S'\), whenever there exists a marking \(\mu\) such that \(S'\cong \mathbf{S}_\mu(S)\), where '\(\cong\)' denotes the usual equivalence relation of isomorphism in the class of sigraphs. It is obvious that '\(\sim\)' is an equivalence relation on the class of all sigraphs, and as such on the class \(\Psi(G)\) of all sigraphs S such that their underlying graphs \(S^u\) are isomorphic to S. Hence, if \(S\sim S'\) we shall say that S and S' are switching equivalent.

Figure 2. Two sigraphs S and S' such that \(S \sim S'\).

Further, two cycles \(C_1\) and \(C_2\) are said to be adjacent cycles if and only if they have at least one vertex in common. A cycle that is an induced subgraph is called chordless cycle.

One can extend the study of a graph equations with respect to isomorphism to a sigraph equations with respect to switching equivalence (Gill and Patwardhan, 1981, 1986; Acharya, 1986). In this paper, we initiate study of a new system of switching equivalence relations, i.e., negation switching invariant, aimed at hopefully facilitating application of results to analyze evolution of structures of social systems due to local interactions. We also obtain in the sequel conditions for which \(S \cong \eta(S)\); infact, it is the subset of the set of solutions of \(S \sim \eta(S)\).

2. Negation switching invariant sigraphs

Given a sigraph S and a positive integer n, the n-path sigraph \((S)_n\) is defined to be a sigraph on the vertex set V(S) of S, with two vertices u and v joined by an edge e = uv in \((S)_n\) provided

there is a u-v path of length n in S and with the sign σn(e) of e defined to be '−' if and only if in every u-v path of length n in S all the edges are negative (as shown in Figure 3). The notion of npath graphs was introduced by Escalante et al. (1974), and various studies concerning this notion may be found in the work of Acharya (1973), Escalante and Montejano (1973, 1974), Harary et al. (1982), Simic (1983), etc. A graph G for which

Figure 3. Showing a sigraph S and its 2-path sigraph (S)² and 3-path sigraph (S)3.

has been termed as n-path invariant graph by Escalante and Montejano (1974), where the explicit solutions to (1) are determined for n = 2, 3. The structure of n-path invariant graphs remain still uninvestigated in literature for all n ≥ 4. Clearly, (S)¹ = S for any sigraph S and hence to solve S ∼ η(S) is the special case for characterizing sigraphs S for n = 1 in (S)ⁿ ∼ η(S). The following result has been already obtained.

Remark 2.1. A sigraph S = (G, σ) is switching equivalent to its negation η(S) if it is a bipartite sigraph.

Towards this end, the following notion is needed: two sigraphs S¹ and S² are said to be weakly isomorphic (e.g., see Sozanski, 1980) or ´ cycle isomorphic (e.g., see Zaslavsky, 1982) if there exists an isomorphism f : S u ¹ → S u 2 such that the sign of every cycle Z in S¹ equals the sign in S² (i.e., f preserves both vertex adjacencies and the signs of the cycles of S¹ and S2), where the sign of any subsigraph of a sigraph is defined as the product of the signs of its edges. The following theorem will also be useful in our further investigation, where Ψ(G) will denote the set of all sigraphs whose underlying graph is G.

Theorem 2.1. (Sozanski, 1980; Zaslavsky, 1982): ´ Given a graph G, any two sigraphs in Ψ(G) are switching equivalent if and only if they are cycle isomorphic.

The following theorem determines the solution to S ∼ η(S).

Theorem 2.2. For a connected sigraph S = (S u , σ), S ∼ η(S) if and only if either

(i) S u is bipartite or

• (ii) there exist subsets \(V_1\) and \(V_2\) of V(S) such that
  • (a) \(S = \langle V_1 \rangle \cup \langle V_2 \rangle\) and \(\langle V_1 \cap V_2 \rangle\) is bipartite,
  • (b) \(\langle V_1 \rangle^u \cong \langle V_2 \rangle^u\) such that degrees of corresponding vertices are preserved in S, and
  • (c) each odd (even) cycle in \(\langle V_1 \rangle\) is of opposite (same) sign to the corresponding cycle in \(\langle V_2 \rangle\).

Proof. Necessity: Let us suppose that \(S \sim \eta(S)\). It is clear that \(S^u \cong (\eta(S))^u\). Thus, there exists a bijection, say f, from the vertex set of \(S^u\) to the vertex set of \((\eta(S))^u\) i.e.,

\[f: V(S^u) \to V((\eta(S))^u)\]

such that f(u) = u and f(v) = v and two vertices u and v are adjacent in \(S^u\) if and only if f(u) and f(v) are adjacent in \((\eta(S))^u\). By Theorem 2, of cycle isomorphism, two sigraphs \(S_1\) and \(S_2\) are switching equivalent if and only if they are cycle isomorphic.

Now \(S \sim \eta(S)\) implies that there exists a bijection \(\psi\) from the set of the cycles of S to the set of cycles of \(\eta(S)\) such that cycles Z and \(\psi(Z)\) are cycle isomorphic. Let \(Z_1, Z_2, \ldots, Z_r\) be cycles in S which corresponds to \(\psi(Z_1), \psi(Z_2), \ldots, \psi(Z_r)\), respectively in \(\eta(S)\). Let \(n_1, n_2, \ldots, n_r\) be the number of edges in \(Z_1, Z_2, \ldots, Z_r\) respectively and \(n'_1, n'_2, \ldots, n'_r\) be the number of negative edges in \(Z_1, Z_2, \ldots, Z_r\) respectively. Since \(S \sim \eta(S)\), we have

\[n'_1 + n'_2 + \dots + n'_r + (n_1 - n'_1) + (n_2 - n'_2) + \dots + (n_r - n'_r) \equiv 0 \pmod{2}\]

\[n_1 + n_2 + \dots + n_r \equiv 0 \pmod{2}\]

This implies either all the cycles in S are of even length or odd cycles in S are even in number. If all the cycles are of even length then \(S^u\) is bipartite.

If S contains odd cycles also, then odd cycles are even in number. Now for every odd cycle \(Z_i\) in S, \(Z_i \not\sim \eta(Z_i)\), but since S is cycle isomorphic to \(\eta(S)\), implies that for each odd cycle \(Z_i\) in S there exists another odd cycle \(Z_i'\) in \(\eta(S)\) such that \(Z_i \sim Z_i'\) in such a manner that vertex adjacencies and sign of other cycles of S and \(\eta(S)\) are preserved. This further implies that there exists another cycle \(Z_{ii}\) in S which is of the same length as \(Z_i\) but with opposite sign. Then, by the above argument, it is clear that there exists another bijection from the vertex set of \(S^u\) to the vertex set of \((\eta(S))^u\), which is different from f and the sigraphs S and \(\eta(S)\) are switching equivalent with respect to this bijection. Let g be such a bijection i.e.,

\[g: V(S^u) \to V((\eta(S))^u)\]

Thus, there exist two vertices \(u,v\in V(S^u)\) such that \(g(u)\neq u\) and two vertices u and v are adjacent in \(S^u\) if and only if g(u) and g(v) are adjacent in \((\eta(S))^u\) and \(S\sim \eta(S)\) with respect to this bijection.

Now, we first choose a cycle, say \(Z_1\), which is odd and keep all the vertices of \(Z_1\) in subset \(V_1\) of V(S). Then, since \(Z_1 \not\sim \eta(Z_1)\) there exists another cycle \(Z_1'\) in \(\eta(S)\) such that \(Z_1 \sim Z_1'\) and vertex adjacencies and sign of other cycles of S and \(\eta(S)\) are preserved. Put the vertices of \(Z_1'\), which are also the vertices of a cycle say \(Z_{11}\) in S, in subset \(V_2\) of V(S). Clearly \(Z_1 \sim \eta(Z_{11})\).

Next, we choose another cycle, say \(Z_2\), in S such that \(Z_2\) is adjacent to \(Z_1\) and \(Z_2\) is different from \(Z_{11}\). If no such \(Z_2\) exists in S, then result is already proved. Next, if \(Z_2\) exists then consider two cases:

Case I: If \(Z_2\) is an odd cycle then by the above argument we can find a cycle \(Z_{22}\) in S such that \(Z_2 \sim \eta(Z_{22})\) and vertex adjacencies and sign of other cycles of S and \(\eta(S)\) are preserved and \(\langle V(Z_1) \cup V(Z_2) \rangle \sim \langle V(\eta(Z_{11})) \cup V(\eta(Z_{22})) \rangle\). Put the vertices of cycle \(Z_2\) in S in subset \(V_1\) and vertices of cycle \(Z_{22}\) in S in subset \(V_2\).

Case II: If \(Z_2\) is an even cycle then again there exists a cycle \(Z_{22}\) in S such that \(Z_2 \sim \eta(Z_{22})\) and \(\langle V(Z_1) \cup V(Z_2) \rangle \sim \langle V(\eta(Z_{11})) \cup V(\eta(Z_{22})) \rangle\). Now \(Z_2\) being an even cycle, the cycle \(Z_2\) may be same as \(Z_{22}\) or it may be distinct.

If \(Z_2\) and \(Z_{22}\) are not distinct, put the vertices of \(Z_2\) or \(Z_{22}\) in both the vertex subsets \(V_1\) and \(V_2\). If \(Z_2\) and \(Z_{22}\) are distinct cycles then put the vertices of \(Z_2\) in \(V_1\) and the vertices of \(Z_{22}\) in \(V_2\).

Continuing in this manner we have a set of chordless cycles \(Z_1, Z_2, \ldots, Z_r\) such that \(\langle V(Z_1) \cup V(Z_2) \cup \cdots \cup V(Z_r) \rangle \sim \langle V(\eta(Z_{11})) \cup V(\eta(Z_{22})) \cup \cdots \cup V(\eta(Z_{rr})) \rangle\), where the vertices of half of the odd cycles in S are in \(V_1\) and the vertices of other half odd cycles are in \(V_2\). The remaining cycles, which are symmetric difference of these cycles, are automatically settled. Thus, by \(S \sim \eta(S)\), it is clear that if \(V(Z_i) \neq V(Z_i')\), then vertices of \(Z_i\) are put in \(V_1\) and vertices of \(Z_i'\) are put in \(V_2\) and if \(V(Z_i) = V(Z_i')\), then vertices of \(Z_i(=Z_i')\) are put in both the subsets \(V_1\) and \(V_2\), where \(V_1' = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(V_1') = V(\)

Next, suppose \(v \in V(S)\) is any vertex (if any) such that v dose not lie in any cycle of S, but adjacent with a vertex which lies on any cycle in S. If the vertex v is such that g(v) = v, then put the vertex v in both the subsets \(V_1\) and \(V_2\).

Now, suppose \(v \in V(S)\) is such that \(g(v) \neq v\). Then, consider two cases. If v is adjacent with a vertex which lies in \(V_1\) (\(V_2\)), then put the vertex v in \(V_1\) (\(V_2\)) and if v is adjacent with the vertex which is in both the subsets \(V_1\) and \(V_2\), then put v in \(V_1\) and \(V_2\) or vice-versa.

Next, we choose another vertex \(v_1\) (if any), which is adjacent with \(v_1\), such that \(v_1\) is not in any cycle of S. Again, if \(g(v_1) = v_1\), then put \(v_1\) in both the subsets \(V_1\) and \(V_2\) and if \(g(v_1) \neq v_1\), then if \(v_1\) is in \(V_1\) (\(V_2\)) put \(v_1\) in \(V_1\) (\(V_2\)). Continuing in this manner we put all the vertices in \(V_1\) or in \(V_2\). Then, \(V_1\) and \(V_2\) are subsets of V(S) such that \(\langle V_1 \rangle^u \cong \langle V_2 \rangle^u\) and \(S = \langle V_1 \rangle \cup \langle V_2 \rangle\). Clearly,

if \(V(Z_i) = V(Z_i')\), then \(Z_i\) cannot be an odd cycle. Thus, there can not be an odd cycle whose vertices are in \(V_1\) and \(V_2\) both and hence \(\langle V_1 \cap V_2 \rangle\) is bipartite. Thus, conditions are necessary.

Sufficiency: If \(S^u\) is bipartite then it is trivially true that \(S \sim \eta(S)\). On the other hand if \(S^u\) is not bipartite then it contains at least one odd cycle. By (ii)(b) there exist two subsets \(V_1\) and \(V_2\) in S such that \(\langle V_1 \rangle^u \cong \langle V_2 \rangle^u\). Since, \(S^u \cong (\eta(S))^u\) and \(V(S) = V(\eta(S))\), the same subsets \(V_1\) and \(V_2\) exist in \(\eta(S)\) also. Also, by the same condition, degrees of corresponding vertices are preserved in \(\eta(S)\) also. It is clear that there exist at least two isomorphism. One where every element is mapped to itself and another where element of \(V_1 - V_2\) of S gets mapped to the element of \(V_2 - V_1\) of S gets mapped to the element of \(S^u\). Thus, there exists a bijection from the vertex set of \(S^u\) to the vertex set of \(S^u\) such that every element in \(S^u\) is not an image of itself in \(S^u\) is not an image of itself in \(S^u\) in the element of \(S^u\) to the vertex set of \(S^u\) to the vertex set of \(S^u\) to the vertex set of \(S^u\) such that every element in \(S^u\) is not an image of itself in \(S^u\) in \(S^u\) to the vertex set of \(S^u\) to same length but of opposite (same) sign. By our bijection there is an odd (even) cycle of same length and same sign in \(S^u\) of \(S^u\). Thus, \(S^u\) and \(S^u\) are cycle isomorphic. Hence, by Theorem 2.1, \(S^u\) and \(S^u\) and \(S^u\) are cycle isomorphic. Hence, by Theorem 2.1, \(S^u\) and \(S^u\) in \(S^u\) in \(S^u\) and \(S^u\) are cycle isomorphic. Hence, by Theorem 2.1, \(S^u\) and \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in \(S^u\) in

Lemma 2.1. For a disconnected sigraph \(S = (S^u, \sigma)\), \(S \sim \eta(S)\) if and only if either

• (i) \(S^u\) is bipartite or
• (ii) there exist subsets \(V_1\) and \(V_2\) of V(S) such that
  • (a) \(S = \langle V_1 \rangle \cup \langle V_2 \rangle\) and \(\langle V_1 \cap V_2 \rangle\) is bipartite,
  • (b) \(\langle V_1 \rangle^u \cong \langle V_2 \rangle^u\) such that degrees of corresponding vertices are preserved in S, and
  • (c) each odd (even) cycle in \(\langle V_1 \rangle\) is of opposite (same) sign to the corresponding cycle in \(\langle V_2 \rangle\).

The result immediately follows from Theorem 2.2.

The following theorem determines the solution to \(S \cong \eta(S)\).

Theorem 2.3. For a given sigraph \(S = (S^u, \sigma)\), \(S \cong \eta(S)\) if and only if the edge set E(S) can be partitioned into two subsets \(E_1\) and \(E_2\) such that \(\langle E_2 \rangle \cong \langle \eta(E_1) \rangle\) and degrees of corresponding vertices are preserved in S.

Proof. Necessity: Let \(S \cong \eta(S)\). We know that the two sigraphs are signed isomorphic if and only if there exists an one-to-one correspondence between the vertices of the two sigraphs such that adjacencies along with signs of the two sigraphs are preserved. Let f be a bijection from the vertex set V(S) to the vertex set \(V(\eta(S))\) i.e.,

\[f:V(S)\to V(\eta(S))\]

such that any two vertices u and v of S are adjacent if and only if f(u) and f(v) are adjacent in \(\eta(S)\) and are of the same signature. Let

\[\sigma^{'}:E(\eta(S))\longrightarrow\{-,+\}\]

Then

\[\sigma(uv) = \sigma'(f(u)f(v))\]

If \(f(u) = u_1\) and \(f(v) = v_1\) such that \(u, v \in V(S)\), then \(f(u) \neq u\) and \(f(v) \neq v\), since otherwise f will not be signed isomorphism. Hence there exist \(u_1, v_1 \in V(\eta(S))\) such that u corresponds to \(u_1\) and v corresponds to \(v_1\) under f and if \(uv \in E(S)\) then \(f(u)f(v) = u_1v_1 \in E(\eta(s))\). Also, \(S \cong \eta(S)\) implies that \(S^u \cong \eta(S)^u\), so there exists a bijection

\[q:V(S^u)\longrightarrow V(\eta(S)^u)\]

such that g(u)=u and g(v)=v but \(\sigma(uv)=-\sigma^{'}(g(u)g(v))=-\sigma^{'}(uv).\)

There also exists another isomorphism g' from vertex set of \(S^u\) to the vertex set of \(\eta(S)^u\) which also preserve adjacencies i.e.,

\[g': V(S^u) \longrightarrow V(\eta(S)^u)\]

such that \(g^{'}(u)=u^{'}\) and \(g^{'}(v)=v^{'}\) and any two vertices u and v are adjacent in S if and only if u' and v' are adjacent in \(\eta(S)\) and \(\sigma(uv)=\sigma^{'}(u^{'}v^{'})\) where \(u,v\in V(S)\) and \(u^{'},v^{'}\in V(\eta(S))\).

Under suitable choice of u' and v'

\[\sigma'(g'(u)g'(v))g'(u)g'(v) = f(u)f(v)\]

and \(\sigma'(u_1v_1) = \sigma'(u'v')\).

Now, we first choose an edge, say \(e_1 = uv\), and keep this edge in subsets \(E_1\) of E(S). Since \(S \cong \eta(S)\) and f is a bijection from the vertex set V(S) to the vertex set \(V(\eta(S))\) such that \(f(u) = u_1\) and \(f(v) = v_1\), so by the definition of isomorphism \(u_1v_1 = e_1'\) is an edge in \(\eta(S)\) and \(\sigma(uv) = \sigma'(u_1v_1)\). If \(u_1v_1\) is an edge in \(\eta(S)\) then, since the vertices of S and \(\eta(S)\) are same and \(S^u \cong \eta(S)^u\), \(u_1v_1 = e_{11}\) is an edge in S and \(\sigma'(u_1v_1) = -\sigma(u_1v_1)\). So put the edge \(u_1v_1 = e_{11}\) of S in subset \(E_2\) of E(S). It is easy to see that u corresponds to \(u_1\), v corresponds to \(v_1\) in S and \(\sigma(uv) = -\sigma(u_1v_1)\) such that \(u, v, u_1, v_1 \in V(S)\).

Next, we choose another edge, say \(e_2\), in S such that it is adjacent to uv and it is different from \(u_1v_1\). Now we can find an edge in S, say \(e_{22}\), such that \(\langle e_1 \cup e_2 \rangle \cong \langle \eta(e_{11}) \cup \eta(e_{22}) \rangle\). Every time we choose an edge in S which is neither selected in subset \(E_1\) nor in \(E_2\) of E(S).

Continuing in this manner we have a set of edges \(e_1, e_2, \ldots, e_r\) and \(e_{11}, e_{22}, \ldots, e_{rr}\) in S such that \(\langle e_1 \cup e_2 \cup \cdots \cup e_r \rangle \cong \langle \eta(e_{11}) \cup \eta(e_{22}) \cup \cdots \cup \eta(e_{rr}) \rangle\). Thus we can partition the edge set E(S) into two subsets \(E_1 = \langle e_1 \cup e_2 \cup \cdots \cup e_r \rangle\) and \(E_2 = \langle \eta(e_{11}) \cup \eta(e_{22}) \cup \cdots \cup \eta(e_{rr}) \rangle\) such that \(\langle E_2 \rangle \cong \langle \eta(E_1) \rangle\) and it is also clear that the degrees of corresponding vertices are same in S.

Sufficiency: Now, let we assume that we can partition the edge set E(S) into two subsets \(E_1\) and \(E_2\) such that \(\langle E_2 \rangle \cong \langle \eta(E_1) \rangle\) and the degrees of corresponding vertices are same in S.

Since, hE2i ∼= hη(E1)i thus there exists an one-to-one correspondence between hE2i and hη(E1)i. Since subsigraph hE1i is isomorphic to hη(E1)i or hE2i and hE2i is isomorphic to hη(E2)i or hE1i in η(S) such that adjacencies are also preserve and degrees of corresponding vertices are same in S. So there exists an isomorphism from the vertex set of V (S) to the vertex set of V (η(S)). Hence, S ∼= η(S), which completes the proof.

Acknowledgement

The author wishes to thank Prof. G. Vijayakumar, T.F.I.R. Bombay, for pointing out the problem in CARDMATH group discussion on signed discrete structure and application, Regional Institute of Education, Mysore and Dr. B.D. Acharya for looking into isomorphism of above signed equation.

References

• [1] R.P. Abelson and M.J. Rosenberg, Symbolic psychilogic: A model of attitudinal cognition, Behav. Sci., 3 (1958), 1–13.
• [2] B.D Acharya, Open-neighborhood graphs, Technical Report Number DAE: 22/8/72G, Indian Institute of Technology, Bombay, May 1973. Also, see: Graph Theory Newsletter, 2(4) (1973).
• [3] B.D. Acharya and S. Joshi, On the complement of an ambisidi-graph, Discrete Math. 15 (2003), 5.
• [4] M. Acharya, Switching-invariant three-path signed graphs, Proc. Symp. On Optimization, Design of experiments and Graph Theory, IIT, Bombay Dec. 15-17 (1986), 342–345.
• [5] M. Acharya and T. Singh, Graceful signed graphs, Czechoslovak Math. J. 54(2) (2004), 291– 302.
• [6] M. Acharya and T. Singh, Graceful signed graphs: II. The case of signed cycles with connected negative sections, Czechoslovak Math. J. 55(130) (2005), 25–40.
• [7] F. Escalante and L. Montejano, Extremal problems concerning n-path connected graphs, Communicaciones Tecnicas, B, CIMAS, National Univ., Mexico 4(60) (1973).
• [8] F. Escalanate, L. Montejano and T. Rojao, A characterization of n-path graphs and of graphs having n-root, J. Combin. Theory Ser. B 16(3) (1974), 282–289.
• [9] F. Esclanate and L. Montejano, Trees and n-path invariant graphs, Graph Theory Newsletter 3(3), 1974.
• [10] J. Fiksel, Dynamic evolution of societal networks, J. Math. Sociol. 7 (1980), 27–46.

• [11] M.K. Gill and G.A. Patwardhan, A characterization of sigraphs which are switching equivalent to their line sigraphs, J. Math. Phys. Sci. 15(6) (1981), 567–571.
• [12] M.K. Gill and G.A. Patwardhan, Switching-invariant two-path sigraphs, Discrete Math. 61 (1986), 189–196.
• [13] F. Harary, On the notion of balance of a signed graph, Michigan Math. J. 2 (1953), 143–146.
• [14] F. Harary, Structural duality, Behav. Sci. 2(4) (1957), 255–265.
• [15] F. Harary, C. Hoede and D. Kadlecek, Graph valued functions related to step graphs, J. Combin. Inform. System Sci. 7(3) (1982), 231–245.
• [16] O. Katai and S. Iwai, Studies on the balancing, the minimal balancing and the minimum balancing processes for social groups with planar and nonplanar graph structures, J. Math. Psych. 18 (1978), 140–176.
• [17] O. Katai and S. Iwai, Characterization of social balance by statistical and finite-state systems theoretical analysis, Proc. Internat. Conf. & Society, Tokyo, (1978), 312–316.
• [18] V.B. Kovchegov, A model of dynamics of group structure of human institutions, J. Math. Sociol. 18(4) (1994), 315–332.
• [19] V.B. Kovchegov, A principle of nonergodicity for modeling of the human groups by nets of probability automata, Proc. 14th IMACS World Congress on Computational and Applied Mathematics, July 11-15, 1994, Georgia Institute of Technology, Atlanta, Georgia, USA, (1994), 787–790.
• [20] S.K. Simic, Graph Equations for line graphs and n th distance graphs, Publ. Instt. Math. (Beograd) 33(47) (1983), 203–216.
• [21] T. Singh, Advances in the theory of signed graphs, Ph.D. Thesis, University of Delhi (Faculty of Technology), 2004.
• [22] T. Sozanski, Enumeration of weak isomorphism classes of signed graphs, ´ J. Graph Theory 4(2) (1980), 127–144.
• [23] D.B. West, Introduction to Graph Theory, Prentice-Hall of India Pvt. Ltd., 1996.
• [24] T. Zaslavsky, Signed graphs, Discrete Math. Appl. 4(1) (1982), 47–74.
• [25] T. Zaslavsky, A mathematical bibliography of signed and gain graphs and allied areas, VII Edition, Electron. J. Combin. #DS8(1998), 157pp.