An algorithmic characterization and spectral analysis of canonical splitting signed graph ξ(Σ)

Abstract

An ordered pair Σ=(Σu,σ) is called the signed graph, where Σu=(V,E) is an underlying graph and σ is a signed mapping, called signature, from E to the sign set {+,−}. A marking of Σ is a function μ:V(Σ)→{+,−}. The canonical marking of a signed graph Σ, denoted μσ, is given asμσ(v)=Πvu∈E(Σ)σ(vu).The canonical splitting signed graph ξ(Σ) of a signed graph Σ is defined as a signed graph ξ(Σ)=(V(ξ),E(ξ)) , with V(ξ)=V(Σ)∪V′, where V′ is copy of a vertex set in V(Σ) s.t. for each vertex u∈V(Σ), take a new vertex u′ and E(ξ) is defined as, join u′ to all the vertices of Σ adjacent to u by negative edge if μσ(u)=μσ(v)=−, where v∈N(u) and by positive edge otherwise. The objective of this paper is to propose an algorithm for the generation of a canonical splitting signed graph, a splitting root signed graph from a given signed graph, provided it exists and to give the characterization of balanced canonical splitting signed graph. Additionally, we conduct a spectral analysis of the resulting graph. Spectral analysis is performed on the adjacency and Laplacian matrices of the canonical splitting signed graph to study its eigenvalues and eigenvectors. A relationship between the energy of the original signed graph Σ and the energy of the canonical splitting signed graph ξ(Σ) is established. • Algorithm to generate canonical splitting signed graph ξ(Σ). • Spectral Analysis is performed for both adjacency and Laplacian matrices of canonical splitting signed graph ξ(Σ).

Keywords

• Graph algorithm