Enumeration and extensions of word-representants

DOI10.1007/978-3-030-28796-2_14zbMATH Open1443.05097arXiv1909.00019OpenAlexW2970342476MaRDI QIDQ5896085FDOQ5896085

Publication date: 7 July 2020

Published in: Discrete Applied Mathematics, Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: Given a finite word

w

over a finite alphabet

V

, consider the graph with vertex set

V

and with an edge between two elements of

V

if and only if the two elements alternate in the word

w

. Such a graph is said to be word-representable or 11-representable by the word

w

; this latter terminology arises from the phenomenon that the condition of two elements

x

and

y

alternating in a word

w

is the same as the condition of the subword of

w

induced by

x

and

y

avoiding the pattern 11. In this paper, we first study minimal length words which word-represent graphs, giving an explicit formula for both the length and the number of such words in the case of trees and cycles. We then extend the notion of word-representability (or 11-representability) of graphs to