Semi-transitivity of directed split graphs generated by morphisms

Iamthong, Kittitat and Kitaev, Sergey (2023) Semi-transitivity of directed split graphs generated by morphisms. Journal of Combinatorics, 14 (1). ISSN 2156-3527 (https://doi.org/10.4310/JOC.2023.v14.n1.a5)

[thumbnail of Iamthon-Kitaev-JoC-2022-Semi-transitivity-of-directed-split-graphs-generated-by-morphisms]
Preview
 Text. Filename: Iamthon_Kitaev_JoC_2022_Semi_transitivity_of_directed_split_graphs_generated_by_morphisms.pdf
Accepted Author Manuscript
License: Strathprints license 1.0
Download (370kB)| Preview

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.

ORCID iDs

Iamthong, Kittitat and Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647;
CORE (COnnecting REpositories)