{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,27]],"date-time":"2026-09-27T23:14:51Z","timestamp":1790550891114,"version":"4.1.0"},"reference-count":23,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2006,10,6]],"date-time":"2006-10-06T00:00:00Z","timestamp":1160092800000},"content-version":"vor","delay-in-days":4023,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Graph Theory"],"published-print":{"date-parts":[[1995,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A digraph is quasi\u2010transitive if there is a complete adjacency between the inset and the outset of each vertex. Quasi\u2010transitive digraphs are interseting because of their relation to comparability graphs. Specifically, a graph can be oriented as a quasi\u2010transitive digraph if and only if it is a comparability graph. Quasi\u2010transitive digraphs are also of interest as they share many nice properties of tournaments. Indeed, we show that every strongly connected quasi\u2010transitive digraphs <jats:italic>D<\/jats:italic> on at least four vertices has two vertices <jats:italic>v<\/jats:italic><jats:sub>1<\/jats:sub> and <jats:italic>v<\/jats:italic><jats:sub>2<\/jats:sub> such that <jats:italic>D<\/jats:italic> \u2013 <jats:italic>v<\/jats:italic><jats:sub>i<\/jats:sub> is strongly connected for <jats:italic>i<\/jats:italic> = 1, 2. A result of tournaments on the existence of a pair of arc\u2010disjoint in\u2010 and out\u2010branchings rooted at the same vertex can also be extended to quasi\u2010transitive digraphs. However, some properties of tournaments, like hamiltonicity, cannot be extended directly to quasi\u2010transitive digraphs. Therefore we characterize those quasi\u2010transitive digraphs which have a hamiltonian cycle, respectively a hamiltonian path. We show the existence of highly connected quasi\u2010transitive digraphs <jats:italic>D<\/jats:italic> with a factor (a collection of disjoint cycles covering the vertex set of <jats:italic>D<\/jats:italic>), which have a cycle of every length 3 \u2266 <jats:italic>k<\/jats:italic> \u2266 |<jats:italic>V<\/jats:italic>(<jats:italic>D<\/jats:italic>)| \u2212 1 through every vertex and yet they are not hamiltonian. Finally we characterize pancyclic and vertex pancyclic quasi\u2010transitive digraphs. \u00a9 1995, John Wiley &amp; Sons, Inc.<\/jats:p>","DOI":"10.1002\/jgt.3190200205","type":"journal-article","created":{"date-parts":[[2007,6,7]],"date-time":"2007-06-07T16:22:48Z","timestamp":1181233368000},"page":"141-161","source":"Crossref","is-referenced-by-count":68,"title":["Quasi\u2010transitive digraphs"],"prefix":"10.1002","volume":"20","author":[{"given":"J\u00f8rgen","family":"Bang\u2010Jensen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jing","family":"Huang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"311","published-online":{"date-parts":[[2006,10,6]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(91)90002-2"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190140310"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90645-V"},{"key":"e_1_2_1_5_2","article-title":"Vertex heaviest paths and cycles in quasi\u2010transitive digraphs","author":"Bang\u2010Jensen J.","journal-title":"Discrete Math."},{"key":"e_1_2_1_6_2","unstructured":"J.Bang\u2010Jensen G.Gutin andJ.Huang A sufficient condition for a complete multipartite digraph to be Hamiltonian. Submitted."},{"key":"e_1_2_1_7_2","unstructured":"J.Bang\u2010JensenandJ.Huang Quasi\u2010kings in quasi\u2010transitive digraphs. Submitted."},{"key":"e_1_2_1_8_2","unstructured":"J.Bang\u2010Jensen G.GutinandA.Yeo Onk\u2010strong andk\u2010cyclic digraphs. Submitted."},{"key":"e_1_2_1_9_2","unstructured":"X.Deng P.Hell andJ.Huang Recognition and representation of proper circular arc graphs in Integer Programming and Combinatorial Optimization Proceeding of the second IPCO conference (Egon Balas G. Cornu\u00e9jols and R. Kannan eds.) (1992)114\u2013121."},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02020961"},{"key":"e_1_2_1_11_2","first-page":"1370","article-title":"Caract\u00e9risation des graphes non orient\u00e9s dont on peut orienter les arr\u011btes de maniere \u00e0 obtenir le graphe d'un relation d'ordre","volume":"254","author":"Ghouil\u00e0\u2010Houri A.","year":"1962","journal-title":"C. R. Acad. Sci. Paris"},{"key":"e_1_2_1_12_2","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"Golumbic M. C.","year":"1980"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/0406020"},{"key":"e_1_2_1_14_2","unstructured":"G.Gutin Paths and cycles in directed graphs. Ph.D. Thesis Tel\u2010Aviv University (1993)."},{"key":"e_1_2_1_15_2","article-title":"Characterizations of vertex pancylic and pancyclic ordinary complete multipartite digraphs","author":"Gutin G.","journal-title":"Discrete Math."},{"key":"e_1_2_1_16_2","first-page":"231","article-title":"Polynomial algorithms for finding hamiltonian paths and cycles in Quasi\u2010transitive digraphs","volume":"10","author":"Gutin G.","year":"1994","journal-title":"Australasian J. Combin."},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-009-5315-4_1"},{"key":"e_1_2_1_18_2","unstructured":"P.HellandJ.Huang Lexicographic orientation and representation algorithms for comparability graphs proepr circular arc graphs and proper interval graphs submitted."},{"key":"e_1_2_1_19_2","unstructured":"P.HellandJ.Huang Linear algorithms for proper circular arc graphs submitted."},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1016"},{"key":"e_1_2_1_21_2","unstructured":"J.Huang Tournament\u2010like oriented graphs. Ph.D. thesis Simon Fraser University (1992)."},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190060307"},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(80)90061-1"},{"key":"e_1_2_1_24_2","first-page":"305","volume-title":"Graph Theory and Combinatorics","author":"Thomassen C.","year":"1984"}],"container-title":["Journal of Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fjgt.3190200205","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.3190200205","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,26]],"date-time":"2023-10-26T21:29:30Z","timestamp":1698355770000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/jgt.3190200205"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,10]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1995,10]]}},"alternative-id":["10.1002\/jgt.3190200205"],"URL":"https:\/\/doi.org\/10.1002\/jgt.3190200205","archive":["Portico"],"relation":{},"ISSN":["0364-9024","1097-0118"],"issn-type":[{"value":"0364-9024","type":"print"},{"value":"1097-0118","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,10]]}}}