Tosha-degree equivalence signed graphs

A graph is an ordered pair Г = (V, E), where V is a set of vertices of Г and E is a collection of pairs of vertices of Г, called edges of Г. For standard terminology and notion in graph theory, we refer the reader to the text-book of Harary [1]. All graphs considered in the paper are finite, simple and connected. The non-standard will be given in this paper as and when required.

In [2], we defined the Tosha-degree of an edge in a graph and Tosha-degree equivalence graph of a graph as follows:

Let a Ite an edge in a graph Г. The Tosh;t-degree of a. denoted by T(a). is the number of edges adjacent to a in Г. with self-loops counted twice. For any edge a in a ₍graph Г. T(a) » 0.

Let Г = (V, E) be a graph and |E| = m. We define a relation S on E as follows: for a, в EE.

a,e = T(a) = T^Y

It is easy to see that S is an equivalence relation on E. Let Ei, E₂,..., Ek be the partition of E in to disjoint classes by the relation $. Let |Ei | = mi, 1 i г к к so that m1 +m₂ +.. . + mk = m.

The equivalence class graph on E defined by S is called Tosha-degree equivalence graph of Г and is denoted by T (Г).

A signed graph is an ordered pair X = (Г, a), where Г = (V, E) is a graph called the ‘underlying graph of X aiid a : E -» { + ,-} is a function. A marking of X is a function p ^: V (^Г) ■ {+,

A signed graph X = (Г,a) is balanced if every cycle in X has an even number of negative edges (see [3]). Equivalently, a signed graph is balanced if product of signs of the edges on every cycle of X is positive.

The following are the fundamental results about balance, the second being a more advanced form of the first. Note that in a bipartition of a set, V = V1 u V2, the disjoint subsets may be empty.

Theorem 1.1. A signed graph X is balanced if and only if either of the following equivalent conditions is satisfied:

• (i)    Its vertex set has a bipartition V = V1 U V2 such that every positive edge joins vertices in V1 or in V2. and every negative edge joins a vertex in V1 and a v ertex in V2 (Harary [3]).

• (ii)    There exists a marking p of its vertices such that each edge uv in Г satissties a(uv) = p(u)p(v). (Sampathkumar [4]).

• 2.    Tosha-Degree Equivalence Signed Graph of a Graph

Two signed graphs X1 aiid X2 are signed isorriorpine (written X1 = X2) if there is a one-to-one correspondence between their vertex sets which preserve adjacency as well as sign.

Given a marking p of a signed graph X = (Г,a). stintching X with re sped, to p is the operation of changing the sign of every edge uv оf X bу p(u)a(uv)p(v). The signed graph obtained in this way is denoted by X^(X) and is cailed the p-switched signed graph or just switched signed graph.

A signed graph X1 = (Г, a) switches to a signed graph X2 = (Г , a ) (or that X1 aiid X2 are switching equivalent) written X1 ~ X2, whenever there exists a marking p оf X1 such that X^(Xi) = X2. Note that Xi ~ X2 implies that Г = Г , since the definition of switching does not involve change of adjacencies in the underlying graphs of the respective signed graphs. Infact, the idea of switching a signed graph was introduced by Abelson and Rosenberg [5] in connection with structural analysis of marking p of a signed graph X.

Two signed graphs X1 = (Г,a) a nd X₂ = (Г , a ) are said to be cycle isomorphic (see [6]) if there exists an isomorphism ф : Г -» Г such that the sign of every cycle Z in X1 equals to the sign of ф(Z) in X₂. The following result is known [6]:

Theorem 1.2 (T. Zaslavsky [6]). Two signed graphs Xi an d X2 with the same underlying graph are switching equivalent if, and only if, they are cycle isomorphic.

One of the important operations on signed graphs involves changing signs of their edges. The negation of a signed graph X, denoted n(X), is obtained by negating the sign of every edge of X, i. e., by changing the sign of every edge to its opposite [7].

In [2], we have defined the Tosha-degree equivalence graph of a graph which is motivated to extend this notion to signed graphs as follows: The Tosha-degree equivalence signed graph of a signed graph X = (Г, a) as a signed graph T (X) = (T (Г), a ). where T (Г) is the under lying-graph of T (X) is the Tosha-degree equivalence graph of Г. where for any edge eie2 i 11 T (X). a (e1e₂) = a(e1 )a(e₂). Hence, we shall call a given signed graph X as Tosha-degree equivalence signed graph if it is isomorphic to the Tosha-degree equivalence signed graph T (X ) of some sigrapli X .

The following result indicates the limitations of the notion of Tosha-degree equivalence signed graphs as introduced above, since the entire class of unbalanced signed graphs is forbidden to be Tosha-degree equivalence signed graphs.

Theorem 2.1. For any signed graph S = (Г,а), its Tosha-degree equivalence signed graph T (S) = (T(Г),a') is balanced.

• <    Let Ej be the set of vertices of Tosha-degree equivalence signed graph T (S) each of which corresponds to a positive edge in S and Ej be the set of vertices of Tosha-degree equivalence signed graph T (S) each of which corresponds to a negative edge in S. Let eiej be any negative edge in T (S). By the definitioii of T(S). the edges ei aiid ej (if’S are not of the same sign and hence as vertices of T (S) they cannot lie in the same part of the partition {Ej,Ej }. On the other 1 land, if the edge eiej is any positive edge of T (S) then, by the definition of T (S) the edges ei aiid ej оf S are of the same sign aiid hence as vertices of T(S) they must both lie in exactly one of the parts of the partition { Ej ,Ej } of the vertex set of T (S). Thus, every negative edge of T (S) has its ends in different parts of this partition whereas no positive edge of T (S) has this property. Therefore, by the well known Partition Criterion for Balance of by Theorem 1.1, it follows that T (S) must be balanced. ▻

For any positive integer k, the k^th iterated Tosha-degree equivalence signed graph, Tk( S) of S is defined as follows:

T ⁰ (S) = S,

T \ S) = T(T k ¹

(S)).

Corollary 2.2. For any signed graph S = (G, a) and for any positive integer k, Tk^ S) is balanced.

Theorem 2.3. For any two signed graphs S1 an d S₂ with the same underlying graph, their Tosha-degree equivalence signed graphs are switching equivalent.

• <    Suppose S1 = (Г, a) a nd S₂ = (Г , a ) be two signed graphs with Г а Г . By Tlieorerri 2.1. T (Si) a nd T (E₂) are balanced and hence, the result follows from Theorem 1.2. ▻

In [2], we have characterize the graphs such that Г = T (Г).

• Theorem 2.4.    Let Г be a connected graph with m edges. Then Г = T (Г) if and only if Г = K3.

In view of the above result, we now characterize those signed graphs that are switching equivalent to their Tosha-degree equivalence signed graphs.

• Theorem 2.5.    For any connected signed graph S = (Г,а) with m edges. Then S ~ T (S) if and only if S is balanced signed graph and Г a K3.

• <    Suppose S - T (S). This irnplics. T (Г) = Г arid hence by Theorem 2.4 we see that Г is isomorphic to complete graph K3. Now, if S is signed graph in which underlying graph Г is isomorphic to K3. Tlieorerri 2.1 implies that T (S) is balanced and hence if S is unbalanced its Tosha-degree equivalence signed graph T (S) being balanced cannot be switching equivalent to S in accordance with T1 leorem 1.2. Therefore. S must be balanced.

Conversely. suppose that S is balanced arid Г is isomorpliic to K3. Then, by Theorem 2.1. T (S) is balanced, the result follows from Theorem 1.2. ▻

By the definition of Tosha-degree of an edge in a graph, Tosha-degree equivalence graph of a graph and Theorem 2.4, we have the following result:

Theorem 2.6. Let Г be a connected graph with m edges. Then Г = T^k (Г) if and only if Г = K3.

In view of the above result, we now characterize those signed graphs that are switching equivalent to their kth iterated Tosha-degree equivalence signed graphs.

Theorem 2.7. For any connected signed graph S = (Г, a) with m edges. Then S ~ Tk (S) if and only if S is balanced signed graph and Г = K3.

For a signed graph S = (Г,а), the T (S) is balanced (Theorem 2.1). We now examine, the conditions under which negation n of T(S) is balanced.

Theorem 2.8. Let S = (Г,а) be a signed graph. If T (Г) is bipartite then n(T (S)) is balanced.

• <    Since, by Theorem 2.1, T (S) is balanced, if each cycle C in T (S) contains even number of negative edges. Also, since T (Г) is bipartite, all cycles have even length; thus, the number of positive edges on any cycle C in T(S) is also even. Hence n(T(S)) is balanced. ▻

• 2.1.    Characterization of Tosha-Degree Equivalence Signed Graphs. The following result characterize signed graphs which are Tosha-degree equivalence signed graphs.

Theorem 2.5 and 2.7 provides easy solutions to two other signed graph switching equivalence relations, which are given in the following results:

Corollary 2.9. For any signed graph S = (Г,а), n(S) ~ T (S) if and only if S is an unbalanced signed graph and Г = K3.

Corollary 2.10. For any signed graph S = (Г, a), n(S) ~ T(n(S)) if and only if S is an unbalanced signed graph and Г = K3.

Corollary 2.11. For any signed graph S = (Г,а), n(S) ~ Tk( S) if and only if S is an unbalanced signed graph and Г = K3.

Corollary 2.12. For any signed graph S = (Г, a), n(S) - Tk (n(S)) if and only if S is an unbalanced signed graph and Г = K3.

Theorem 2.13. A signed graph S = (Г,а) is a Tosha-degree equivalence signed graph if and only if S is balanced signed graph and its underlying graph Г is a Tosha-degree equivalence graph.

• < Suppose that S is balanced and Г is a Tosha-degree equivalence graph. Then there exists a graph Г such that T (Г ) = Г. Since S is balanced, by Theorem 1.1, there exists a marking gof Г such that each edge uv in S satisfies a(uv) = ^(u)^(v). Now consider the signed graph S = (Г , a ). where for any edge e ii 1 Г . a (e) is the marking of the c-orresponding vertex in Г. Then clearly, T (S ) = S. Hence S is a Tosha-degree equivalence signed graph.

Conversely, suppose that S = (F,a) is a Tosha-degree equivalence signed graph. Then there exists a signed graph S = (Г , a ) such that T (S ) = S. Hence Г is the Tosha-degree equivalence graph and by Theorem 2.1, S is balanced. ▻

Acknowledgment: The authors would like to extend their gratitude to the referee for the valuable suggestions.