文章基本信息

标题：New characterizations of proper interval bigraphs
本地全文：下载
作者：Ashok Kumar Das ; Ashok Kumar Das ; Ritapa Chakraborty 等
期刊名称：AKCE International Journal of Graphs and Combinatorics
印刷版ISSN：0972-8600
出版年度：2015
卷号：12
期号：1
页码：47-53
DOI：10.1016/j.akcej.2015.06.007
语种：English
出版社：Elsevier
摘要：Abstract 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.
关键词：KeywordsenAstral triple of edgesMonotone consecutive arrangementZero partitionableCircularly compatible 1’sDominating pair of vertices