Semi-transitivity of directed split graphs generated by morphisms

Kittitat Iamthong, Sergey Kitaev

Research output: Contribution to journalArticlepeer-review

3 Downloads (Pure)

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 languageEnglish
Number of pages26
JournalJournal of Combinatorics
Volume14
Issue number1
Early online date19 Aug 2022
DOIs
Publication statusE-pub ahead of print - 19 Aug 2022

Keywords

  • semi-transitive orientation of graphs
  • split graphs
  • semi-transitive split graphs
  • directed graphs
  • word-representable graphs

Fingerprint

Dive into the research topics of 'Semi-transitivity of directed split graphs generated by morphisms'. Together they form a unique fingerprint.

Cite this