zbMATH — the first resource for mathematics

Quasi-transitive digraphs. (English) Zbl 0832.05048
A digraph is quasi-transitive if whenever \(x\), \(y\) and \(z\) are distinct vertices such that \(x\) dominates \(y\) and \(y\) dominates \(z\), then \(x\) and \(z\) are adjacent. Quasi-transitive digraphs share many nice properties of tournaments. It is shown that every strongly connected quasi-transitive digraph \(D\) on \(n\geq 4\) vertices contains two vertices \(x\) and \(y\) such that \(D- x\) and \(D- y\) are strongly connected. Hamiltonian, pancyclic and vertex pancyclic quasi-transitive digraphs are characterized. The authors point out that their characterizations of quasi-transitive digraphs having hamiltonian cycle or path, respectively, do not seem to imply polynomial algorithms. Their conjecture that such algorithms exist has been confirmed by the reviewer [Australas. J. Comb. 10, 231-236 (1994; Zbl 0817.05061)].
Reviewer: G.Gutin (Odense)

05C20 Directed graphs (digraphs), tournaments
05C38 Paths and cycles
05C45 Eulerian and Hamiltonian graphs
05C75 Structural characterization of families of graphs
Full Text: DOI
[1] Bang-Jensen, J. Combin. Theory B51 pp 1– (1991) · Zbl 0659.05052 · doi:10.1016/0095-8956(91)90002-2
[2] Bang-Jensen, J. Graph Theory 14 pp 371– (1990)
[3] Bang-Jensen, Discrete Math. 100 pp 1– (1992)
[4] Bang-Jensen, Discrete Math.
[5] , and , A sufficient condition for a complete multipartite digraph to be Hamiltonian. Submitted.
[6] and , Quasi-kings in quasi-transitive digraphs. Submitted. · Zbl 0955.05048
[7] and , On k-strong and k-cyclic digraphs. Submitted. · Zbl 0873.05047
[8] , and , Recognition and representation of proper circular arc graphs, in Integer Programming and Combinatorial Optimization, Proceeding of the second IPCO conference (Egon Balas, G. Cornuéjols, and R. Kannan, eds.) (1992) 114–121.
[9] Gallai, Acta Math. Acad. Sci. Hung. 18 pp 25– (1967)
[10] Ghouilà-Houri, C. R. Acad. Sci. Paris 254 pp 1370– (1962)
[11] Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980). · Zbl 0541.05054
[12] Gutin, SIAM J. Discrete Math. 6 pp 270– (1993)
[13] Paths and cycles in directed graphs. Ph.D. Thesis, Tel-Aviv University (1993).
[14] Gutin, Discrete Math.
[15] Gutin, Australasian J. Combin. 10 pp 231– (1994)
[16] Comparability graphs, in Graphs and Order (ed. ), Nato ASI Series C. vol. 147, D. Reidel (1985), 3–40. · doi:10.1007/978-94-009-5315-4_1
[17] and , Lexicographic orientation and representation algorithms for comparability graphs, proepr circular arc graphs, and proper interval graphs, submitted. · Zbl 0835.05064
[18] and , Linear algorithms for proper circular arc graphs, submitted.
[19] Huang, J. Combin. Theory B63 pp 200– (1995) · Zbl 0820.05029 · doi:10.1006/jctb.1995.1016
[20] Tournament-like oriented graphs. Ph.D. thesis, Simon Fraser University (1992).
[21] Skrien, J. Graph Theory 6 pp 309– (1980)
[22] Thomassen, J. Combinatorial Theory B28 pp 142– (1980) · Zbl 0435.05026 · doi:10.1016/0095-8956(80)90061-1
[23] Connectivity in tournaments. Graph Theory and Combinatorics, ed., Academic Press, London (1984) 305–313.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.