An Algorithmic Characterization of Splitting Signed Graph

A signed graph (also known as sigraph) S is a graph G′ where every edge y have value s′(y)∈{−1,+1} known as its sign function and is denoted as S=(G′,s′). Given a sigraph S=(V,E,σ), for every vertex v∈V(S), take a new vertex v′. Join v′ to all vertices of S adjacent to v such that, σΛ(uv′)=σ(uv), u∈N(v). The sigraph Λ(S)=(VΛ,EΛ,σΛ) thus produced is called the splitting sigraph of S. Here we define an algorithm to produce a splitting sigraph and root splitting sigraph from a given sigraph, if it exists, in O(n4) steps.