Semi-transitivity of directed split graphs generated by morphisms

A directed graph is semi-transitive if and only if it is acyclic and for any directed path $u_1 \to u_2 \to \dotsm \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 \lt 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 ${\lbrace -1,0,1 \rbrace}$ with a single natural condition.

Keywords

word-representable graph, semi-transitive orientation, permutation

2010 Mathematics Subject Classification

Primary 05C62. Secondary 68R15.

Full Text (PDF format)

Received 28 May 2021

Accepted 7 February 2022

Published 19 August 2022