Short proofs for interval digraphs (Q1377823): Difference between revisions
From MaRDI portal
Latest revision as of 10:32, 28 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Short proofs for interval digraphs |
scientific article |
Statements
Short proofs for interval digraphs (English)
0 references
8 March 1998
0 references
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''.
0 references
intersection digraph
0 references
interval digraph
0 references
adjacency matrix
0 references