Semi-transitivity of directed split graphs generated by morphisms

2021/08/12 by Iamthong, Kittitat, Kitaev, Sergey · 4 citations
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2108.05483

Abstract

A directed graph is semi-transitive if and only if it is acyclic and for any directed path u₁→ u₂→ ⋯ → u_t, t ≥ 2, either there is no edge from u₁ to u_t or all edges u_i→ u_j 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.

Cited by

• Forbidden Induced Subgraph Characterization of Word-Representable Co-bipartite Graphs
• Forbidden Induced Subgraph Characterization of Word-Representable Split Graphs
• Word-Representable Co-Bipartite Graphs: Vertex Ordering, Representation Number, Speed, and Entropy
• On the word-representability of K_m-K_n graphs

Related

• On semi-transitive orientability of split graphs
• Forbidden Induced Subgraph Characterization of Word-Representable Split Graphs
• Transitivity conditions in infinite graphs
• Transitive path decompositions of Cartesian products of complete graphs
• Transitive decompositions of graphs and their links with geometry and origami