Representing split graphs by words

Chen, Herman Z.Q. and Kitaev, Sergey and Saito, Akira (2020) Representing split graphs by words. Discussiones Mathematicae Graph Theory, 42 (4). pp. 1263-1280. ISSN 1234-3099 (https://doi.org/10.7151/dmgt.2344)

[thumbnail of Chen-etal-DMGT-2020-Representing-split-graphs-by]
Preview
 Text. Filename: Chen_etal_DMGT_2020_Representing_split_graphs_by.pdf
Accepted Author Manuscript
Download (182kB)| Preview

Abstract

There is a long line of research in the literature dedicated to word-representable graphs, which generalize several important classes of graphs. However, not much is known about word-representability of split graphs, another important class of graphs. In this paper, we show that threshold graphs, a subclass of split graphs, are word-representable. Further, we prove a number of general theorems on word-representable split graphs, and use them to characterize computationally such graphs with cliques of size 5 in terms of 9 forbidden subgraphs, thus extending the known characterization for word-representable split graphs with cliques of size 4. Moreover, we use split graphs, and also provide an alternative solution, to show that gluing two word-representable graphs in any clique of size at least 2 may, or may not, result in a word-representable graph. The two surprisingly simple solutions provided by us answer a question that was open for about ten years.

ORCID iDs

Chen, Herman Z.Q., Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647 and Saito, Akira;
  • Item type:Article
    ID code:72873
    Dates:
    Date
    Event
    20 July 2020
    Published
    17 June 2020
    Accepted
    13 November 2019
    Submitted
    Notes:Copyright © 2020 University of Zielona Góra
    Subjects:Science > Mathematics
    Department:Faculty of Science > Mathematics and Statistics
    Depositing user: Pure Administrator
    Date deposited:24 Jun 2020 11:16
    Last modified:11 Nov 2024 12:44
    Related URLs:
    URI:https://strathprints.strath.ac.uk/id/eprint/72873
CORE (COnnecting REpositories)