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

A directed graph is called (m, k)-transitive if for every directed path x0x1…xm there is a directed path y0y1…yk such that x0=y0, xm=yk, and {yi|0⩽i⩽k} ⊂{xi|0⩽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(n2) that tests (m, k)-transitivity in such graphs on n vertices for every m and k=1, and for m=3 and k=2.