Short proofs for interval digraphs

Directed graphs (digraphs), tournaments (05C20) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Structural characterization of families of graphs (05C75)

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.

Recommendations

Cites work

Cited in

(15)

This page was built for publication: Short proofs for interval digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1377823)