Signed degree sequences in signed multipartite graphs

Year 2015, Volume: 44 Issue: 5, 1099 - 1108, 01.10.2015

S. Pirzada T. A. Naikoo

Abstract

A signed k-partite graph (signed multipartite graph) is a k-partite graph in which each edge is assigned a positive or a negative sign. If G(V1, V2, · · · , Vk) is a signed k-partite graph with Vi ={vi1,vi2,··· ,vini}, 1 ≤ i ≤ k, the signed degree of vij is sdeg(vij) = dij = d+ij− d−ij, where 1≤i≤k,1≤j≤ni and d+ij(d−ij)is the number of positive (negative) edges incident with vij. The sequences αi = [di1,di2,··· ,dini], 1 ≤ i ≤ k, are called the signed degree sequences of G(V1,V2,··· ,Vk). The set of distinct signed degrees of the vertices in a signed k-partite graph G(V1, V2, · · · , Vk) is called its signed degree set. In this paper, we characterize signed degree sequences of signed k-partite graphs. Also, we give the existence of signed k-partite graphs with given signed degree sets.

Keywords

Signed graphs, signed multipartite graph, signed degree, signed set

References

• .. .