Enumeration and Extensions of Word-representants
Given a finite word over a finite alphabet , consider the graph with vertex set and with an edge between two elements of if and only if the two elements alternate in the word . Such a graph is said to be word-representable or 11-representable by the word ; this latter terminology arises from the phenomenon that the condition of two elements and alternating in a word is the same as the condition of the subword of induced by and 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 -representability of graphs, for any pattern on two letters. We prove that every graph is -representable for any pattern on two letters (except for possibly one class of ). Finally, we pose a few open problems for future consideration.