Word-representability of Toeplitz graphs

Cheon, Gi-Sang and Kitaev, Sergey and Kim, Jinha and Kim, Minki (2019) Word-representability of Toeplitz graphs. Discrete Applied Mathematics. pp. 1-18. ISSN 0166-218X (In Press)

[img] Text (Cheon-etal-DAM2019-Word-representability-of-Toeplitz-graphs)
Cheon_etal_DAM2019_Word_representability_of_Toeplitz_graphs.pdf
Accepted Author Manuscript
Restricted to Repository staff only until 21 July 2020.
License: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 logo
Download (294kB) | Request a copy from the Strathclyde author

    Abstract

    Distinct letters x and y alternate in a word w if after deleting in w all letters but the copies of x and y we either obtain a word of the form xyxy... (of even or odd length) or a word of the form yxyx... (of even or odd length). A graph G=(V,E) is word-representable if there exists a word w over the alphabet V such that letters x and y alternate in w if and only if xy is an edge in E. In this paper we initiate the study of word-representable Toeplitz graphs, which are Riordan graphs of the Appell type. We prove that several general classes of Toeplitz graphs are word-representable, and we also provide a way to construct non-word-representable Toeplitz graphs. Our work not only merges the theories of Riordan matrices and word-representable graphs via the notion of a Riordan graph, but also it provides the first systematic study of word-representability of graphs defined via patterns in adjacency matrices. Moreover, our paper introduces the notion of an infinite word-representable Riordan graph and gives several general examples of such graphs. It is the first time in the literature when the word-representability of infinite graphs is discussed.

    Author(s):Cheon, Gi-Sang, Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647, Kim, Jinha and Kim, Minki
    Item type:Article
    ID code:68963
    Keywords:Toeplitz graph, word-representable graph, Riordan graph, pattern, Electronic computers. Computer science, Computer Science(all)
    Subjects:Science > Mathematics > Electronic computers. Computer science
    Department:Faculty of Science > Computer and Information Sciences
    Depositing user: Pure Administrator
    Date deposited:22 Jul 2019 14:36
    Last modified:21 Nov 2019 03:00
    Related URLs:
    URI:https://strathprints.strath.ac.uk/id/eprint/68963
    Export data:
    CORE (COnnecting REpositories)