Word-representability of Toeplitz graphs

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

Research output: Contribution to journalArticle

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.
LanguageEnglish
Pages1-18
Number of pages18
JournalDiscrete Applied Mathematics
Publication statusAccepted/In press - 21 Jul 2019

Fingerprint

Representability
Otto Toeplitz
Graph in graph theory
Alternate
Odd
Infinite Words
Infinite Graphs
Adjacency Matrix
If and only if
Distinct

Keywords

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

Cite this

Cheon, G-S., Kitaev, S., Kim, J., & Kim, M. (Accepted/In press). Word-representability of Toeplitz graphs. Discrete Applied Mathematics, 1-18.
Cheon, Gi-Sang ; Kitaev, Sergey ; Kim, Jinha ; Kim, Minki. / Word-representability of Toeplitz graphs. In: Discrete Applied Mathematics. 2019 ; pp. 1-18.
@article{c73180c819e04d25994941ff88c03c8c,
title = "Word-representability of Toeplitz graphs",
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.",
keywords = "Toeplitz graph, word-representable graph, Riordan graph, pattern",
author = "Gi-Sang Cheon and Sergey Kitaev and Jinha Kim and Minki Kim",
year = "2019",
month = "7",
day = "21",
language = "English",
pages = "1--18",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",

}

Word-representability of Toeplitz graphs. / Cheon, Gi-Sang; Kitaev, Sergey; Kim, Jinha; Kim, Minki.

In: Discrete Applied Mathematics, 21.07.2019, p. 1-18.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Word-representability of Toeplitz graphs

AU - Cheon, Gi-Sang

AU - Kitaev, Sergey

AU - Kim, Jinha

AU - Kim, Minki

PY - 2019/7/21

Y1 - 2019/7/21

N2 - 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.

AB - 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.

KW - Toeplitz graph

KW - word-representable graph

KW - Riordan graph

KW - pattern

UR - https://www.sciencedirect.com/journal/discrete-applied-mathematics

M3 - Article

SP - 1

EP - 18

JO - Discrete Applied Mathematics

T2 - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -