Circular-arc digraphs: A characterization. (English) Zbl 0689.05025
A graph is a circular-arc graph if it is the intersection graph of a family of arcs on a circle. The paper gives an adjacency matrix characterization of a circular-arc digraph defined as the intersection digraph of a family of order pairs of arcs on a circle. The paper also gives another characterization of the interval digraphs.
Reviewer: W.K.Chen
MSC:
| 05C20 | Directed graphs (digraphs), tournaments |
References:
| [1] | Discrete Math. 55 (1985) |
| [2] | Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980). · Zbl 0541.05054 |
| [3] | Guttman, Am. Sociol. Rev. 9 pp 139– (1944) |
| [4] | Riguet, C R Acad. Sci. Paris 232 pp 1729– (1951) |
| [5] | Sen, J. Graph Theory 13 pp 189– (1989) |
| [6] | Tucker, Bull. Am. Math. Soc. 76 pp 1257– (1970) |
| [7] | Tucker, Pacific J. Math. 39 pp 535– (1971) · Zbl 0226.05125 · doi:10.2140/pjm.1971.39.535 |
| [8] | Tucker, Discrete Math. 7 pp 167– (1974) |
| [9] | Tucker, SIAM J. Appl. Math. 29 pp 493– (1975) |
| [10] | Circular-arc graphs: New uses and a new algorithm. Theory and Application of Graphs. Lecture Notes in Mathematics 642, Springer-Verlag, New York (1978) pp. 580–589. |
| [11] | Parameters of partial orders and graphs: Packing, covering, and representation. Graphs and Order. Reidel (1985) pp. 267–350. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
