n-th power signed graphs

Abstract

A signed graph (marked graph) is an ordered pair S = (G, σ) (S = (G, μ)), where G = (V,E) is a graph called the underlying graph of S and σ : E → {+, −} (μ : V → {+, −}) is a function. The n-th power graph of a graph G = (V,E) is a graph Gn = (V,E＇), with same vertex set as G, and has two vertices u and v are adjacent if their distance in G is n or less. Analogously, one can define the nth power signed graph of a signed graph S = (G, σ). Consider the marking μ on vertices of S defined as follows: each vertex v ∈ V , μ(v) is the product of the signs on the edges incident at v. The nth power signed graph of S is a signed graph Sn = (Gn, σ＇) where Gn is the underlying graph of Sn, where for any edge e = uv 2 Gn, 0(uv) = μ(u)μ(v). It is shown that for any signed graph S, its nth power signed graph Sn is balanced. We then give structural characterization of n-th power signed graphs. Two signed graphs S1 and S2 are switiching equivalent written S1 ~ S2, whenever there exists a marking μ of S1 such that the signed graph Sμ(S1) obtained by changing the sign of every edge of S1 to its opposite whenever its end vertices are of opposite signs, is isomorphic to S2. Further, we present solutions of some signed graph switching equations involving the line signed graph, complement and n-th power signed graph operations. One such equation (L(S))n ~ S generalizes a result of P. Siva Kota Reddy and M. S. Subramanya (L(S) ~ S) [11].