Semi-transitivity of directed split graphs generated by morphisms

Kittitat Iamthong; Sergey Kitaev

paper

Semi-transitivity of directed split graphs generated by morphisms

arXiv:2108.05483

Abstract

A directed graph is semi-transitive if and only if it is acyclic and for any directed path $u_{1} \to u_{2} \to \dots \to u_{t}$ , $t \geq 2$ , either there is no edge from $u_{1}$ to $u_{t}$ or all edges $u_{i} \to u_{j}$ exist for $1 \leq i < j \leq t$ . In this paper, we study semi-transitivity of families of directed split graphs obtained by iterations of morphisms applied to the adjacency matrices and giving in the limit infinite directed split graphs. A split graph is a graph in which the vertices can be partitioned into a clique and an independent set. We fully classify semi-transitive infinite directed split graphs when a morphism in question can involve any $n \times m$ matrices over ${- 1, 0, 1}$ with a single natural condition.

28 pages, 1 figure