Arc Signed Graphs of Oriented Graphs

Abstract

A signed graph is an unoriented graph with a given partition \(E = E^+ \bigcup E^-\) of its edge-set. We define the arc signed graph \({A}(G)\) of an oriented graph \(G\) (G has no multiple arcs, opposite arcs, and loops). The arc signed graphs are similar to the line graphs. We prove both a Krausz-type characterization and a forbidden induced subgraph characterization (like the theorem of Beineke and Robertson on line graphs). Unlike line graphs, there are infinitely many minimal forbidden induced subgraphs for the arc signed graphs. Nevertheless, the arc signed graphs are polynomially recognizable. Also, we obtain a result similar to Whitney’s theorem on line graphs.