New characterizations of proper interval bigraphs

A proper interval bigraph is a bigraph where to each vertex we can assign a closed interval such that the intervals can be chosen to be inclusion free and vertices in the opposite partite sets are adjacent when the corresponding intervals intersect. In this paper, we introduce the notion of astral triple of edges and along the lines of characterization of interval graphs via the absence of asteroidal triple of vertices we characterize proper interval bigraphs via the absence of astral triple of edges. We also characterize proper interval bigraphs in terms of dominating pair of vertices as defined by Corneil et al. Tucker characterized proper circular arc graphs in terms of circularly compatible 1's of adjacency matrices. Sen and Sanyal characterized adjacency matrices of proper interval bigraphs in terms of monotone consecutive arrangement. We have shown an interrelation between these two concepts. (C) 2015 Kalasalingam University. Production and Hosting by Elsevier B.V.