Abstract
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.
| Language | English |
|---|---|
| Pages | 1-18 |
| Number of pages | 18 |
| Journal | Discrete Applied Mathematics |
| Publication status | Accepted/In press - 21 Jul 2019 |
Fingerprint
Keywords
- Toeplitz graph
- word-representable graph
- Riordan graph
- pattern
Cite this
}
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 journal › Article
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 -