Semi-transitivity of directed split graphs generated by morphisms

DOI10.4310/JOC.2023.V14.N1.A5MaRDI QIDQ2167564zbMATH OpenOpenAlexFDO

Authors Kittitat Iamthong, Sergey Kitaev

Publication date 25 August 2022

Published in Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2108.05483

zbMATH Keywords

permutationsemi-transitive orientationword-representable graph

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Combinatorics on words (68R15)

Abstract: A directed graph is semi-transitive if and only if it is acyclic and for any directed path $u_{1}ightarrow{u}_{2}ightarrowcdotsightarrow{u}_t$, $tgeq2$, either there is no edge from $u_1$ to $u_t$ or all edges $u_{i}ightarrow{u}_j$ exist for $1leqi<jleqt$. 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 $nimesm$ matrices over $-1,0,1$ with a single natural condition.

Recommendations

• Semi-transitive graphs
• Characterization of \((m,1)\)-transitive and \((3,2)\)-transitive semi- complete directed graphs
• scientific article; zbMATH DE number 6930585
• Directed graphs of inner translations of semigroups
• scientific article; zbMATH DE number 3970787
• scientific article; zbMATH DE number 94906
• Directed graphs and combinatorial properties of semigroups
• Semi-transitive orientations and word-representable graphs
• Word-representability of split graphs generated by morphisms
• Semiregular automorphisms of edge-transitive graphs

Cited in

(4)

• On semi-transitive orientability of split graphs
• Segment transit function of the induced path function of graphs and its first-order definability
• On the word-representability of K_m-K_n graphs
• Word-representable co-bipartite graphs: representation number, speed, and entropy

This page was built for publication: Semi-transitivity of directed split graphs generated by morphisms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2167564)