Characterization of (m, 1)-transitive and (3,2)-transitive semi-complete directed graphs

✍ Scribed by Zsolt Tuza

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 875 KB
• Volume: 135
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(94)00060-v

✦ Synopsis

A directed graph is called (m, k)-transitive if for every directed path x0x1 . ..x. there is a directed path y,y, . ..yt such that x0 =y ,,, x,=yl,, and {yiIO<iik}c{xiIO<i<m}.

We describe the structure of those (m, 1)-transitive and (3,2)-transitive directed graphs in which each pair of vertices is adjacent by an arc in at least one direction, and present an algorithm with running time O(n') that tests (m, k)-transitivity in such graphs on n vertices for every m and k=l, and for m=3 and k=2.