Negation switching invariant 3-Path signed graphs

摘要

Formally, a signed graph (sigraph) S is a pair (G, σ) that consists of a graph G = (V, E) and a sign mapping or signature s from E to the sign group {+, -}. Given a sigraph S and a positive integer t, the t-path sigraph (S)t of S is a sigraph whose vertex set is V(S) and two vertices are adjacent if and only if there exist a path of length t between these vertices and then by defining its sign st(e) to be '-' if and only if in every such path of length t in S all the edges are negative. The negation η(S) of a sigraph S is a sigraph obtained from S by reversing the sign of every edge of S. Two sigraphs S_1 and S_2 on the same underlying graph are switching equivalent if it is possible to assign signs '+' ('plus') or '-' ('minus') to the vertices of S_1 such that by reversing the sign of each of its edges that has received opposite signs at its ends one obtains S_2. In this paper, we characterize sigraphs whose negations are switching equivalent to their t-path sigraphs for t = 3.