# Characterization of 2-Path Product Signed Graphs with Its Properties

Authors: Deepa Sinha; Deepakshi Sharma
Journal: Computational Intelligence and Neuroscience
 (2017)

---

## Abstract

Asigned graph is a simple graph where each edge receives a sign positive or negative. Such graphs are mainly used in social sciences where individuals represent vertices friendly relation between them as a positive edge and enmity as a negative edge. In signed graphs, we define these relationships (edges) as of friendship (“+” edge) or hostility (“-” edge). A2-path product signed graphS#^S of a signed graph S is defined as follows: the vertex set is the same as S and two vertices are adjacent if and only if there exists a path of length two between them in S. The sign of an edge is the product of marks of vertices in S where the mark of vertex u in S is the product of signs of all edges incident to the vertex. In this paper, we give a characterization of 2-path product signed graphs. Also, some other properties such as sign-compatibility and canonically-sign-compatibility of 2-path product signed graphs are discussed along with isomorphism and switching equivalence of this signed graph with 2-path signed graph.


---

## Body

## 1. Introduction

Signed graph forms one of the most vibrant areas of research in graph theory and network analysis due to its link with behavioural and social sciences. The earliest appearance of signed graphs can be traced back to Heider [1] and Cartwright [2]. From that time to recently, signed theory has evolved rapidly with signed graphs being linked to algebra [3–5], social networks [6, 7], other models [8, 9], and graph spectra [10] to name few. In graph theory, itself signed graphs have been used to define many properties and new concepts. In [11, 12] the signed graph of line signed graphs is discussed, whereas [13, 14] talks about common edge signed graphs. The work in [15, 16] generalises the (k,d)-graceful graphs to signed graphs. The colouring of signed graphs is reported in [17–19]. The connection between the intersection graphs of neighborhood and signed graphs has also been studied [20–24]. Recently a Coxeter spectral analysis and a Coxeter spectral classification of the class of edge-bipartite graphs (that is a class of signed (multi)graphs) is developed in the papers [25–27] in relation to Lie theory problems, quasi Cartan matrices, Dynkin diagrams, Hilbert’s X Problem, combinatorics of Coxeter groups, and the Auslander-Reiten theory of module categories and their derived categories. In this paper, we were mainly driven to carry out work in the area of signed graphs derived from 2-path product operations, which primarily deals with the structural reconfiguration of the structure of dynamical systems under prescribed rules and the rules are designed to address a variety of interconnections among the elements of the system. We have obtained some theoretical results (some of which are presented in [28]) with a hope of building necessary conceptual resources for applications. For standard terminology and notation in graph theory one can refer to Harary [29] and West [30] and for signed graph literature one can read Zaslavsky [19, 31, 32]. Throughout the text, we consider finite, undirected graph with no loops or multiple edges.Asigned graph is an ordered pair S=(Σ,σ), where Σ is a graph Σ=(V,E), called the underlying graph of S and σ:E→{+,-} is a function from the edge set E of Σ into the set {+,-}, called thesignature (or sign in short) of S. Alternatively, the signed graph can be written as S=(V,E,σ), with V, E, and σ in the above sense. A signed graph isall-positive (resp.,all negative) if all its edges are positive (negative); further, it is said to behomogeneous if it is either all-positive or all negative andheterogeneous otherwise. Thepositive (negative) degree of a vertex 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). Thenegation of a signed graph η(S) is obtained by reversing the sign of edges of S. Let v be an arbitrary vertex of a graph S. We denote the set consisting of all the vertices of Σ adjacent to v by N(v). This set is called the neighborhoodset of v and sometimes we call it as neighborhood of v. A markedsignedgraph is an ordered pair Sμ=(S,μ) where S=(Σ,σ) is a signed graph and μ:V(Σ)→{+,-} is a function from the vertex set V(Σ) of Σ into the set {+,-}, called a marking of S. MS denotes the set of all markings on vertices of S. For any vertex v∈S,μ1(v)=∏u∈N(v)‍σ(uv) is calledcanonical marking. The marking on the vertices will be specified in the whole text as the case may be.N
∗
(
t
)
=
{
v
1
μ
∈
(
V
(
S
μ
)
)
:
t
v
is  an  edge  with  sign
μ
}, N∗+(t)={v+∈(V(Sμ)):tvis  an  edge}, and N∗-(t)={v-∈(V(Sμ)):tvis  an  edge}. A vertex with a marking μ is denoted by vμ. Acycle in a signed graph S is said to bepositive if the product of the signs of its edges is positive or, equivalently, if the number of negative edges in it is even. A cycle which is not positive is said to benegative.A signed graph isline balanced orbalanced if all its cycles are positive. The partition criterion to characterize the balance property of a signed graph is given by Harary. A marked graph isvertex or point balanced if it does not contain odd number of negative vertices. A signed graph S issign-compatible [35] if there exists a marking μ of its vertices such that the end vertices of every negative edge receive “−” marks in μ and no positive edge in S has both of its ends assigned “−” mark in μ; it issign-incompatible otherwise. A canonically marked graph S is said to becanonically sign-compatible (orC-sign-compatible) if end vertices of every negative edge receive “−” sign and no positive edge has both of its ends assigned “−” under μ.The idea ofswitching a signed graph was introduced by Abelson and Rosenberg [36] in connection with structural analysis of social behaviour and may be formally stated as follows: given a marking μ of a signed graph S,switchingS with respect to μ is the operation of changing the sign of every edge of S to its opposite whenever its end vertices are of opposite signs in Sμ (also see Gill and Patwardhan [37, 38]). The signed graph obtained in this way is denoted by (S)μ and is called the μ-switched signed graph or justswitched signed graph when the marking is clear from the context. Further, a signed graph S1switches to signed graphS2 (or that they are switching equivalent to each other), written as S1~S2, whenever there exists μ∈MS1 such that (S1)μ≅S2, where “≅” denotes the isomorphism between any two signed graphs in the standard sense. Two signed graphs S1 and S2 arecycle isomorphic if there exists an isomorphism f:Σ1→Σ2, where Σ1 and Σ2 are underlying graph of S1 and S2, respectively, such that the sign of every cycle Z in S1 equals the sign of f(Z) in S2.Assume thatS=(V,E,σ) is a signed graph. We associate with S the2-path signed graph [39] S#S=(V,E′,σ′) defined as follows: the vertex set is same as the original signed graph S and two vertices u,v∈V(S#S), are adjacent if and only if there exists a path of length two in S. The edge uv∈V(S#S) is negative if and only if all the edges in all the two paths in S are negative otherwise the edge is positive (see Figure 1). The2-path product signed graphS#^S=(V,E′,σ′) [40] is defined as follows: The vertex set is same as the original signed graph S and two vertices u,v∈V(S#^S), are adjacent if and only if there exists a path of length two in S. The sign σ′(uv)=μ1(u)μ1(v),μ1 is canonical marking (see Figure 2).Figure 1
A signed graph and its 2-path signed graph.Figure 2
A signed graph and its 2-path product signed graph.Property 1 (see [39]).
A 2-subset{vi,vj} in a neighborhood of a vertex in a given signed graph S has property P if {vi-,vj-}⊂N∗(vk) for some i,j,k and for each N(t) containing vi,vj, {vi-,vj-}⊂N∗(t).In the first section, we give a characterization of 2-path product signed graph, followed by a theorem of finding the degree of each vertex inS#^S. Also, we find when a 2-path product graph is isomorphic and switching equivalent to its negation. Next, we find when S#^S is all negative for a given S. The following two sections are dedicated to signed graph properties sign-compatibility and canonical-sign-compatibility. The last section deals with the isomorphism and switching equivalence of the two types of 2-path graphs of signed graphs.


## 2. Characterization of 2-Path Product Signed Graph

We require the following theorems for the characterization of 2-path product signed graph.Theorem 2 (see [41]).
A signed graphS is vertex balanced if and only if it is possible to assign signs to the edges of S such that the mark of any vertex u is equal to the product of the signs of the edges incident to u.The following characterization of 2-path graphs was given by Acharya and Vartak.Theorem 3 (see [42]).
A connected graphΣ with vertices vi,i=1,…,n is of the 2-path graph form Σ=H#H, with some graph H if and only if Σ contains a collection of complete subgraphs Σ1,Σ2,…,Σn such that for each i,j=1,…,n(i)
vi∉Σi;(ii)
vi∈Σj⇔vj∈Σi;(iii)
vivj∈Σ and there exists Σk containing vivj.Theorem 4 (see [39]).
A connected sigraphS with vertices vi,i=1,…,n is a 2-path sigraph of some sigraph S′ if and only if S contains a collection of complete subsigraphs S1,S2,…,Sn with marked vertices viμ,μ∈{+,-} such that, for each i,j=1,…,n, the following hold:(i)
viμ∉Si;(ii)
viμ1∈Sj⇔vjμ2∈Si,i≠j,μ1=μ2;(iii)
vivj∈E(S) with sign σ; then there exists Sk containing viμi,vjμj where μi,μj∈{+,-} and if σ(vi,vj)=- then {vi,vj} is a P pair in Sk.The following proposition is evident from [43, 44].Proposition 5.
2-path product signed graph of a signed graphS is always balanced.We give a characterization for 2-path product signed graph.Theorem 6.
A connected signed graphS with vertices vi,i=1,…,n is of the 2-path product signed graph form S=S′#^S′ with some signed graph S′ if and only if the underlying graph Σ is a 2-path graph and S is both line balanced and vertex balanced.Proof.
Necessity. Suppose S is of the 2-path product signed graph form S=S′#^S′ with vertices v1,v2,…,vn. Now from Theorem 3, there exist n complete subsigned graphs such that (i), (ii), and (iii) hold. Let us consider the set N(v) of neighborhood of a vertex v in S′. For each vertex v in S′ there is a neighborhood N(v), hence n such subsets of neighborhoods. Clearly since we consider open neighborhood, v∉N(v), also if a vertex u∈N(v), then uv is an edge in S and hence v∈N(u). And if uv is an edge in S then u and v are adjacent to a vertex w in S′. That is u,v∈N(w) such that σ(uv)=μ1(u)μ1(v) since each vertex has a marking in S′. We know that S′ is a canonically marked signed graph; thus each vertex has a marking μ1. Now let N∗(vi) be the neighborhood of a vertex vi with marked vertices retaining the marking from S′. Then clearly since all three properties (i), (ii), and (iii) of Theorem 3 are satisfied and also by Theorem 2, and Proposition 5, S is line balanced and vertex balanced.
Sufficiency. Let S be a given signed graph such that its underlying graph Σ is a 2-path graph and S is both line balanced and vertex balanced. Then by Theorem 3, it can be written as the union of n complete subsigned graphs S1,S2,…,Sn of marked vertices such that for each i,j=1,…,n, (i), (ii), and (iii) hold. Now associate a vertex vi∉Si to Si and join vi to all the vertices in Si,i=1,…,n and giving the edge vivj sign as that of the product of marking on vi and vj where vj∈Si. Let the signed graph thus obtained be S′. Next we show that S′#^S′≅S. Obviously Σ′#^Σ′≅Σ, where Σ′ and Σ are underlying graph of S′ and S, respectively. Let vivj be an edge S with the sign σ; then σ=μ1(vi)μ1(vj), where μ1(vi) and μ1(vj) are markings on vi and vj, respectively. By hypothesis, vivj∈Sk for some k. Hence we will associate a vertex vk to Sk and let its marking be μ1. By definition, the sign of edge vivj in S′#^S′ is σ′,σ′=μ1(vi)μ1μ1(vj)μ1. That is σ′=σ=μ1(vi)μ1(vj). Therefore, S′ is the signed graph such that S′#^S′≅S.The characterization of 2-path signed graph in Theorem4 provides us with a mechanism to check if a given signed graph is 2-path of some signed graph, which is discussed in Algorithm 1. This has been rigorously studied elsewhere in the author’s contribution which is fully devoted to 2-path signed graphs and its properties. Thus Algorithm 2 using Algorithm 1 detects if the given signed graph is 2-path product signed graph and find the original signed graph. In Algorithm 2, we use the adjacency matrix A={a[i][j]:i,j≤n} and its order n to find the original signed graph. Algorithm 3 is used to find the 2-path product signed graph for a given signed graph.Algorithm 1:To check if the given signed graph is a 2-path of some other signed graph.
Input. The adjacency matrix An×n={aij∈{-1,0,+1}:1≤i,j≤n}
Output. If A is a 2-path for some signed graph A′ then returns A′.
Process
(1) Collect all the cliquesD for each vertex n, using Bron-Kerbosch algorithm [33].
(2) Mark every vertex by + and then − in each clique.
(3) CalculateB, which represent the all possible combinations generated by each marked vertex from the
clique.
(4)fort=1 to size(B)do
(5)   SelectBt∈B
(6)fork=1 to ndo
(7)     Selectm∈Bt&&n′∈Bt
(8)ifa[m][n′]≠0  then
(9)E(k)=Bt
(10)fork=1 to ndo
(11)forl=1 to ndo
(12)ifm(k)+∈Blthen
(13)C[k][l]=1
(14)else
(15)ifm(k)-∈Blthen
(16)C[k][l]=-1
(17)else
(18)m(k)-∉Bl
(19)C[k][l]=0
(20)fork=1 to ndo
(21)forj=1 to ndo
(22)ifC[k][k]==0&&C[k][j]==C[j][k]then
(23)         go to (25)
(24)else
(25)         go to (23)
(26) For all the combinations of elementary swamping operations on either rows or columns inA, repeat (4).
(27) If all the combinations are checked and no such matrixC is obtained then no such graph exist.
(28) If such a signed graph exist thenC is the adjacency matrix of required signed graph whose 2-path signed
graph isS.Algorithm 2:To check if the given signed graph is a 2-path product of some other signed graph.
Input. The adjacency matrix A of signed graph S and dimension n
Output. If S is a 2-path for some signed graph then returns its adjacency matrix A′.
Process
(1) We use Algorithm1 to detect if A is a 2-path signed graph.
(2) Use algorithm in [34] to check if S is balanced.
(3)fori=1 to ndo
(4)d[i]=1;forj=1 to ndo
(5)ifa[i][j]≠0then
(6) d[i]=d[i]∗a[i][j];
(7)f=1;
(8)fori=1 to ndo
(9)f=f∗d[i]
(10)iff=-1then
(11)   The given signed graph is not a 2-path product signed graph
(12)else
(13)   The given signed graph is a 2-path product signed graphAlgorithm 3:Algorithm to obtain a 2-path product signed graph for a given signed graph.
Input. Adjacency matrix A and dimension n.
Output. Adjacency matrix of 2-path signed graph
Process
(1)  Enter the ordern and adjacency matrix A of for a given signed graph S.
(2)  Collect all theqP pairs for given signed graph S.
(3)fori=1 to ndo
(4)d[i]forj=1 to ndo
(5)b[i][j]=0ifa[i][j]≠0then
(6)d[i]=d[i]∗a[i][j];
(7)fori=1 to ndo
(8)forj=1 to ndo
(9)fork=1 to ndo
(10)if(a[i][j]≠0)&&(a[i][k]≠0)then
(11)if(d[k]∗d[j]=-1)then
(12)b[k][j]=-1
(13)b[j][k]=-1
(14)     else
(15)b[k][j]=1
(16)b[j][k]=1Theorem 7.
Ifuμ1∈V(Sμ1),μ1∈{+,-} being the canonical marking of a vertex u, then the degree of the vertex u in S#^S, for a given signed graph S, is given by the following:(i)
Ifμ1=+ then positive degree of u in S#^S=⋃u+∈N∗xN∗+x-u and the negative degree of u=|⋃u+∈N∗(x)(N∗-(x)-{u})|.(ii)
Ifμ1=- then positive degree of u in S#^S=⋃u-∈N∗xN∗-x-u and the negative degree is ⋃u-∈N∗xN∗+x-u.Proof.
By Theorem6 the neighborhoods of a vertex of S gives the edges in S#^S. That is, if u,v∈N∗(x) for some x∈V(S), then uv is an edge in S#^S. Thus ⋃u∈N∗(x)(N∗(x)-{u}) gives the number of vertices which form an edge with u in S#^S. And since the marking is canonical in S thus positive edges in S#^S are given by vertices with same marking. Thus a vertex uμ1,μ1∈{+,-} in V(S#^S) is given by the following:(i)
Ifμ1=+ then positive degree of u in S#^S=⋃u+∈NxN∗+x-u and the negative degree of u=⋃u+∈N∗xN∗-x-u.(ii)
Ifμ1=- then positive degree of u in S#^S=⋃u-∈N∗xN∗-x-u and the negative degree is ⋃u-∈N∗xN∗+x-u.Theorem 8.
S
#
^
S
≅
η
(
S
)
#
^
η
(
S
), if and only if S is a signed graph with each vertex of even degree.Proof.
Necessity. Let S#^S≅η(S)#^η(S); then clearly the underlying graph Σ of S is such that Σ#^Σ≅η(Σ)#^η(Σ). Also since S is a canonically marked signed graph with each vertex of even degree, the mark on every vertex will be the product of edges incident to it. Let if possible v be a vertex with x number of positive edges incident to v and y be the number of negative edges incident to it. Then one of the following cases arises.
Case
1. Let x be even; then y is also even since the total number of edges incident to v is even. In negation of S, y will again be even (since x is even in S). Thus both retain the same marking for v.
Case
2. Let x be odd then y is odd. Clearly μ1(v)=-; also μ1(v) in η(S) is again negative. Thus in both S#^S and η(S)#^η(S) the marking of v is −.
Clearly, since marking on each vertex remains the same so their 2-path product signed graphs remain isomorphic.
Sufficiency. Let S#^S≅η(S)#^η(S). Let if possible v be a vertex with odd degree. Let x be the number of positive edges incident to v and y be the negative edges incident to v; then the following cases arise: (i)
Ifx is odd then y is even. Consequently, v receives a positive marking in S, but in its negation the number of negative edges becomes odd and hence the sign is reversed.(ii)
Ifx is even then y is odd. The marking in S and η(S) is again reversed.Thus if the signed graph has odd degree vertices then the 2-path product graphs of S and η(S) are not isomorphic, which is a contradiction.Corollary 9.
For any signed graphS, S#^S~η(S)#^η(S).Proof.
Clearly,Σ#^Σ≅η(Σ)#^η(Σ), where Σ is underlying graph of S. Next we know that S#^S is always balanced, for every signed graph S. Thus all cycles are positive and have even number of negative edges. Thus both S#^S and η(S)#^η(S) will possess cycles with even number of negative edges. Thus S#^S~η(S)#^η(S).Theorem 10.
A 2-path product signed graphS#^S of a given signed graph S is all negative if and only if S is either a cycle of length 4m or a signed path and S does not contain a subsigned path u+,wμ1,v+ or u-,wμ1,v-, in S where μ1∈{+,-}.Proof.
Necessity. Let for a given S its 2-path product signed graph S#^S be all negative. Clearly, the signed graph S can be a tree or a cycle. Now if S is not a cycle or tree then S#^S will consist of cliques which can not be all negative since cliques always consist of a cycle of length three which can never be all negative as 2-path product signed graphs are always balanced. Clearly, 2-path graph of a cycle of odd length is self-isomorphic. Thus the cycle of odd length can not generate all negative 2-path product graphs. The 2-path graphs of cycles of even length say 2m are disjoint cycles of length m each. So if m is odd then also the 2-path product signed graph can never be all negative. Thus, a cycle of length 4m can generate all negative 2-path product signed graphs. To produce all negative 2-path product signed graph S#^S, S can not have subsigned path u+,wμ1,v+ or u-,wμ1,v-, on any subsigned path since then uv will be a positive edge in S#^S.
Also if there is a treeS with a vertex of degree greater than two, then clearly it gives rise to a clique containing cycles of length three in S#^S, thus having at least one positive edge. Hence the tree can not have a vertex of degree greater than two. Thus, it is a signed path.
Sufficiency. let S is either a cycle of length 4m or a signed path and S does not contain a subsigned path u+,wμ1,v+ or u-,wμ1,v-, where μ1∈{+,-}. Clearly S#^S will be disjoint cycles in case of cycle except for m=1 where it will be two disjoint signed paths. And in case of signed path S#^S will be disjoint paths. And since always for any subsigned path u,w,v in S, u, and v will occupy opposite mark in S#^S, thus it makes edge uv negative in S#^S. Thus S#^S is all negative.


## 3. Sign-Compatibility of 2-Path Product Signed Graphs

In this section, we give a characterization of sign-compatibility for 2-path product signed graphs.Theorem 11 (see [35]).
A signed graphS is sign-compatible if and only if S does not contain a subsigned graph isomorphic to either of the two signed graphs in Figure 3, S1 formed by taking the path P4:x,u,v,y with both the edges xu and vy negative and the edge uv positive, and S2 formed by taking S1 and identifying the vertices x and y.Figure 3
Acharya and Sinha two forbidden subsigned graphs for a sign-compatible signed graph.Theorem 12.
A 2-path product signed graphS#^S of a signed graph S is sign-compatible if and only if (i)
S does not contain a heterogeneous canonically marked triangle or K1,3;(ii)
S does not consist of the canonically marked subsigned path P7:u+,wμ1,v-,xμ1,y-,zμ1,t+ or η(P7):u-,wμ1,v+,xμ1,y+,zμ1,t-, where μ1∈{+,-}.Proof.
Necessity. Let 2-path product signed graph S#^S of a signed graph S be sign-compatible. To prove (i) and (ii), let S consist of a heterogeneous marked triangle u,v,w,u; then there exist two vertices with same mark and one vertex with different mark. Clearly the 2-path product signed graph S#^S will contain triangle u,v,w,u with two negative edges and one positive edge. Thus S#^S will not be sign-compatible, which is a contradiction. Again if S contains a heterogeneous canonically marked K1,3 then S#^S will consist of a forbidden triangle S1 in Figure 3. Hence (i) holds. Let if possible S consist of the canonically marked subsigned path P7:u+,wμ1,v-,xμ1,y-,zμ1,t+ or η(P7):u-,wμ1,v+,xμ1,y-,zμ1,t-, where μ1∈{+,-}. Then S#^S will contain a forbidden S2 in Figure 3; thus S#^S will not be sign-compatible which is a contradiction to our assumption. Hence (ii) holds.
Sufficiency. Let (i) and (ii) hold. To show S#^S is sign-compatible, let if possible S#^S not be sign-compatible. Then S#^S must consist of subsigned graph isomorphic to Figure 3, which is not possible as then either (i) or (ii) does not hold true. Hence S#^S is sign-compatible.


## 4. C-Sign-Compatibility of 2-Path Product Signed Graphs

This section gives the C-sign-compatibility of 2-path product signed graphs.Proposition 13 (see [45]).
Every C-sign-compatible signed graph is sign-compatible.Theorem 14 (see [45]).
A signed graphS=(Σ,σ), is C-sign-compatible if and only if the following holds for S: (i)
For every vertexv∈V(S) either d-(v)=0 or d-(v)=1(mod2) and(ii)
For every positive edgeek=vivj in S either d-(vi)=0 or d-(vj)=0.Theorem 15.
A 2-path product signed graphS#^S of a signed graph S is C-sign-compatible if and only if (i)
S is sign-compatible;(ii)
S does not contain a subsigned path A=u-,wμ1,v-, of vertices u,w,v where μ1∈{+,-};(iii)
if there exist a subsigned pathu+,wμ1,v+ of vertices u,w,v in S; then either d-(u)=0 or d-(v)=0, where μ1∈{+,-};Proof.
Necessity. Let S#^S be C-sign-compatible then clearly it is sign-compatible by Proposition 13. Let us suppose S contains a subsigned graph u-,wμ1,v-; then clearly uv is a positive edge in S#^S such that d-(u)≠0 and d-(v)≠0, which is a contradiction to the fact that S#^S is C-sign-compatible. Hence S does not contain subsigned path u-,wμ1,v-.
Let there exist a subsigned pathu+,wμ1,v+ on vertices u,w,v in S, such that d-(u)≠0 and d-(v)≠0. Then uv is a positive edge in S#^S with both the vertices having negative degrees which is a contradiction to Theorem 14. Thus (i), (ii), and (iii) hold.
Sufficiency. Let (i), (ii), and (iii) hold. Then clearly for each positive edge uv in S#^S either d-(u)=0 or d-(v)=0. Hence by Theorem 14, S#^S is C-sign-compatible.


## 5. Isomorphism and Switching Equivalence ofS#S and S#^S

In this section, we give the switching equivalent and isomorphism for the two definitions of 2-path signed graphs.Theorem 16 (see [46]).
Given a graphG, any two signed graphs are switching equivalent if and only if they are cycle isomorphic.Theorem 17 (see [39]).
For a signed graphS of order n, its 2-path signed graph S#S is balanced if and only if for all sequences of vertices x1,x2,…,xN,1≤N≤n in S such that x1,x2∈N(t1);x2,x3∈N(t2);…;x1,xN∈N(tN) for some t1,t2,…,tN∈V(S); then the pairs xi,xi+1∈N(ti),1≤i≤N having property P are even in each sequence.Theorem 18.
The 2-path signed graphS#S and 2-path product graph S#^S are switching equivalent if and only if S#S is balanced.Proof.
Necessity. if S#S and S#^S are switching equivalent then they are cycle isomorphic and hence S#S is balanced.
Sufficiency. Clearly, Σ#^Σ≅Σ#Σ. Next, we know that S#^S is always balanced. For balanced S#S, each cycle of S#^S and S#S will be positive which implies that S#^S and S#S will be cycle isomorphic. Thus, by Theorem 16, S#^S and S#S are switching equivalent.Theorem 19.
The 2-path signed graphS#S and 2-path product graph S#^S are isomorphic, if and only if there exists subsigned path u+,wμ1,v- or u-,wμ1,v+,μ1∈{+,-} in S; then {u,v}, satisfies P property.Proof.
Necessity. For a signed graph S, let its 2-path signed graph S#S and 2-path product graph S#^S be isomorphic; here if uv is a negative (positive) in S#S then it is negative in S#^S. All the pair of vertices {u,v} are negative in S#S and have propertyP. If there exist subsigned path u+,wμ1,v- and u-,wμ1,v+ where μ1∈{+,-} in S then uv is a negative edge in S#^S and thus {u,v} satisfies propertyP.
Sufficiency. Let there exist subsigned path u+,wμ1,v- and u-,wμ1,v+ in S then {u,v} has propertyP. To show 2-path signed graph S#S and 2-path product graph S#^S are isomorphic. Clearly Σ#^Σ≅Σ#Σ, Σ being the underlying graph of S. Thus we need to show that the sign convention remains the same in S#S and S#^S. This is true since the end vertices of every negative edge of S#^S have property P and hence uv is a negative edge in S#S. And thus 2-path signed graph S#S and 2-path product graph S#^S are isomorphic.


## 6. Conclusion

In this paper, we have worked on 2-path product signed graph of a given signed graphS. A 2-path product signed graph is the signed graph where the vertex set is same as the original signed graph S and two vertices u,v∈V(S#^S) are adjacent if and only if there exists a path of length two in S. The sign σ′(uv)=μ1(u)μ1(v),μ1 being canonical marking. We give its algorithmic characterization along with its properties like sign-compatibility and C-sign-compatibility. Also, we find the isomorphism of 2-path product signed graph and its negation. We next find isomorphism of 2-path signed graph and 2-path product signed graphs.



---

*Source: 1235715-2017-07-06.xml*