An embedding technique in the study of word-representability of graphs

Huang, Sumin and Kitaev, Sergey and Pyatkin, Artem (2024) An embedding technique in the study of word-representability of graphs. Discrete Applied Mathematics, 346. pp. 170-182. ISSN 0166-218X (https://doi.org/10.1016/j.dam.2023.12.017)

[thumbnail of Huang-etal-DAM-2023-An-embedding-technique-in-the-study-of-word-representability-of-graphs]
Preview
 Text. Filename: Huang-etal-DAM-2023-An-embedding-technique-in-the-study-of-word-representability-of-graphs.pdf
Final Published Version
License: Creative Commons Attribution 4.0 logo
Download (456kB)| Preview

Abstract

Word-representable graphs, which are the same as semi-transitively orientable graphs, generalize several fundamental classes of graphs. In this paper we propose a novel approach to study word-representability of graphs using a technique of homomorphisms. As a proof of concept, we apply our method to show word-representability of the simplified graph of overlapping permutations that we introduce in this paper. For another application, we obtain results on word-representability of certain subgraphs of simplified de Bruijn graphs that were introduced recently by Petyuk and studied in the context of word-representability.

ORCID iDs

Huang, Sumin, Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647 and Pyatkin, Artem;
  • Item type:Article
    ID code:87745
    Dates:
    Date
    Event
    31 March 2024
    Published
    23 December 2023
    Published Online
    14 December 2023
    Accepted
    28 August 2023
    Submitted
    Subjects:Science > Mathematics
    Department:Faculty of Science > Mathematics and Statistics
    Depositing user: Pure Administrator
    Date deposited:09 Jan 2024 13:01
    Last modified:11 Nov 2024 14:10
    URI:https://strathprints.strath.ac.uk/id/eprint/87745
CORE (COnnecting REpositories)