Short proofs for interval digraphs
type: Item
instance of: scholarly article
title: Short proofs for interval digraphs
zbMATH Open document ID: 0884.05044
DOI: 10.1016/S0012-365X(97)81840-7
author: Douglas B. West
published in: Discrete Mathematics
publication date: 1998-03-08T00:00:00Z
review text: The intersection digraph of a collection \(\{(S_v,T_v)\}\) of ordered pairs of sets indexed by a set \(V\) has vertex set \(V\) and an edge directed from \(u\) to \(v\) iff \(S_u\cap T_v\neq\varnothing\). For vertex \(v\), \(S_v\) and \(T_v\) are respectively the source set and the sink set. When the source sets and sink sets are intervals, the digraph is said to be an interval digraph; when the intervals are all of the same length, the digraph is said to be a unit interval digraph. ``Interval digraphs were characterized in [\textit{M. Sen, S. Das, A. B. Roy}, and \textit{D. B. West}, Interval digraphs: An analogue of interval graphs, J. Graph Theory 13, No. 2, 189-202 (1989; Zbl 0671.05039)] and in [\textit{M. Sen, S. Das}, and \textit{D. B. West}, Circular-arc digraphs: A characterization, J. Graph Theory 13, No. 5, 581-592 (1989; Zbl 0689.05025)], and unit interval digraphs were characterized in [\textit{M. Sen} and \textit{B. K. Sanyal}, Indifference digraphs: A generalization of indifference graphs, SIAM J. Discrete Math. 7, No. 2, 157-165 (1994; Zbl 0798.05025)]. This note presents shorter proofs of the adjacency matrix characterizations of these classes''.
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 1110075
zbMATH Keywords: intersection digraph
zbMATH Keywords: interval digraph
zbMATH Keywords: adjacency matrix
reviewed by: William G. Brown
MaRDI profile type: Publication
cites work: Connection digraphs and second-order line digraphs
cites work: Composite measurement
cites work: Q3663338
cites work: Q4871039
cites work: Q5804173
cites work: Q5588432
cites work: Interval digraphs: An analogue of interval graphs
cites work: Circular‐arc digraphs: A characterization
cites work: Indifference Digraphs: A Generalization of Indifference Graphs and Semiorders
cites work: The recognition of indifference digraphs and generalized semiorders
cites work: Characterizing circular-arc graphs
cites work: Matrix characterizations of circular-arc graphs
description: scientific article; zbMATH DE number 1110075