Word-representability of split graphs generated by morphisms

Iamthong, Kittitat (2022) Word-representability of split graphs generated by morphisms. Discrete Applied Mathematics, 314. pp. 284-303. ISSN 0166-218X (https://doi.org/10.1016/j.dam.2022.02.023)

[thumbnail of Iamthong-DAM-2022-Word-representability-of-split-graphs-generated-by-morphisms]
Text. Filename: Iamthong_DAM_2022_Word_representability_of_split_graphs_generated_by_morphisms.pdf
Final Published Version
License: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 logo

Download (382kB)| Preview


A graph G=(V,E) is word-representable if and only if there exists a word w over the alphabet V such that letters x and y, x≠y, alternate in w if and only if xy∈E. A split graph is a graph in which the vertices can be partitioned into a clique and an independent set. There is a long line of research on word-representable graphs in the literature, and recently, word-representability of split graphs has attracted interest. In this paper, we first give a characterization of word-representable split graphs in terms of permutations of columns of the adjacency matrices. Then, we focus on the study of word-representability of split graphs obtained by iterations of a morphism, the notion coming from combinatorics on words. We prove a number of general theorems and provide a complete classification in the case of morphisms defined by 2 × 2 matrices.