On 132-representable graphs

Alice L.L. Gao, Sergey Kitaev, Philip B. Zhang

Research output: Contribution to journalArticle

29 Downloads (Pure)

Abstract

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. Word-representable graphs are the subject of a long research line in the literature, and they are the main focus in the recently published book "Words and Graphs" by Kitaev and Lozin. A word w = w1...wn avoids the pattern 132 if there are no 1 ≤ i1 < i2 < i3 ≤ n such that wi1 < wi3 < wi2. The theory of patterns in words and permutations is a fast growing area.
A recently suggested research direction is in merging the theories of word-representable graphs and patterns in words. Namely, given a class of pattern-avoiding words, can we describe the class of graphs represented by the words? We say that a graph is 132-representable if it can be represented by a 132-avoiding word. We show that each 132-representable graph is necessarily a circle graph. Also, we show that any tree and any cycle graph are 132-representable. Finally, we provide explicit 132-avoiding representations for all graphs on at most five vertices, and also describe all such representations, and enumerate them, for complete graphs.
Original languageEnglish
Pages (from-to)105-118
JournalAustralasian Journal of Combinatorics
Volume69
Issue number1
Publication statusAccepted/In press - 19 Jul 2017

Keywords

  • word-representable graph
  • pattern-avoiding word
  • circle graph
  • tree
  • complete graph
  • cycle graph

Fingerprint Dive into the research topics of 'On 132-representable graphs'. Together they form a unique fingerprint.

  • Cite this

    Gao, A. L. L., Kitaev, S., & Zhang, P. B. (Accepted/In press). On 132-representable graphs. Australasian Journal of Combinatorics, 69(1), 105-118.