Contents Online

# Journal of Combinatorics

## Volume 14 (2023)

### Number 1

### Semi-transitivity of directed split graphs generated by morphisms

Pages: 111 – 138

DOI: https://dx.doi.org/10.4310/JOC.2023.v14.n1.a5

#### Authors

#### 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 \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.

Received 28 May 2021

Accepted 7 February 2022

Published 19 August 2022