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]
Preview
 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

Abstract

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.

  • Item type:Article
    ID code:80756
    Dates:
    Date
    Event
    15 June 2022
    Published
    29 March 2022
    Published Online
    22 February 2022
    Accepted
    4 March 2021
    Submitted
    Subjects:Science > Mathematics
    Department:Faculty of Science > Mathematics and Statistics
    Depositing user: Pure Administrator
    Date deposited:17 May 2022 13:02
    Last modified:11 Nov 2024 13:28
    URI:https://strathprints.strath.ac.uk/id/eprint/80756
CORE (COnnecting REpositories)