Word-representability of Toeplitz graphs

Gi-Sang Cheon, Sergey Kitaev, Jinha Kim, Minki Kim

Research output: Contribution to journalArticlepeer-review

1 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)96-105
Number of pages10
JournalDiscrete Applied Mathematics
Volume270
Early online date8 Aug 2019
DOIs
Publication statusPublished - 1 Nov 2019

Keywords

  • Toeplitz graph
  • word-representable graph
  • Riordan graph
  • pattern

Cite this