Abstract
A directed graph is semi-transitive if and only if it is acyclic and for any directed path u1 → u2 → ··· → ut, t ≥ 2, either there is no edge from u1 to ut or all edges ui → uj exist for 1 ≤ i < j ≤ 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×m matrices over {−1,0,1} with a single natural condition.
| Original language | English |
|---|---|
| Number of pages | 26 |
| Journal | Journal of Combinatorics |
| Volume | 14 |
| Issue number | 1 |
| Early online date | 19 Aug 2022 |
| DOIs | |
| Publication status | E-pub ahead of print - 19 Aug 2022 |
Keywords
- semi-transitive orientation of graphs
- split graphs
- semi-transitive split graphs
- directed graphs
- word-representable graphs