Word-representability of Toeplitz graphs

DOI10.1016/J.DAM.2019.07.013MaRDI QIDQ2334044zbMATH OpenOpenAlexFDO

Authors Gi-Sang Cheon, Jinha Kim, Sergey Kitaev, Min-Ki Kim

Publication date 6 November 2019

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1907.09152, https://strathprints.strath.ac.uk/68963/

zbMATH Keywords

patternRiordan graphToeplitz graphword-representable graph

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

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 $xyxycdots$ (of even or odd length) or a word of the form $yxyxcdots$ (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.

Recommendations

• A comprehensive introduction to the theory of word-representable graphs
• Word-Representable Graphs: a Survey
• On representable graphs

Cites work

• 3-coloring in time
• A comprehensive introduction to the theory of word-representable graphs
• Coloring circle graphs
• Enumerating split-pair arrangements
• scientific article; zbMATH DE number 6118217 (Why is no real title available?)
• scientific article; zbMATH DE number 3851153 (Why is no real title available?)
• scientific article; zbMATH DE number 125465 (Why is no real title available?)
• New results on word-representable graphs
• Riordan graphs I: structural properties
• Semi-transitive orientations and word-representable graphs
• THE PERKINS SEMIGROUP HAS CO-NP-COMPLETE TERM-EQUIVALENCE PROBLEM
• Toeplitz graph decomposition
• Word problem of the Perkins semigroup via directed acyclic graphs.
• Words and graphs

Cited in

(8)

• On graphs representable by pattern-avoiding words
• Word-representability of split graphs generated by morphisms
• A comprehensive introduction to the theory of word-representable graphs
• Solving computational problems in the theory of word-representable graphs
• Word-Representable Graphs: a Survey
• '-Rauzy graphs for infinite arrays
• On semi-transitive orientability of circulant graphs
• On semi-transitive orientability of triangle-free graphs

This page was built for publication: Word-representability of Toeplitz graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2334044)