An Algorithmic Characterization of sigraphs whose second iterated line sigraphs and common-edge sigraphs are switching equivalent

摘要

A signed graph (or sigraph in short) S is a graph G where the edges are weighted either +1 or – 1 called the signs of the edges. For a given sigraph, a special kind of structure called common-edge sigraph and second iterated line sigraph exists in literature which has been shown to be isomorphic to each other when the considered sigraph is only positively signed. Particularly, this paper concentrates on algorithmically characterizing sigraphs whose commonedge sigraphs and second iterated line sigraphs remains invariant under switching due to Abelson and Rosenberg and an algorithm to obtain commmon-edge sigraph and second iterated line sigraph in O(n~3) steps.