2021/04/30 by Iamthong, Kittitat · 5 citations
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2104.14872
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.