Picture of neon light reading 'Open'

Discover open research at Strathprints as part of International Open Access Week!

23-29 October 2017 is International Open Access Week. The Strathprints institutional repository is a digital archive of Open Access research outputs, all produced by University of Strathclyde researchers.

Explore recent world leading Open Access research content this Open Access Week from across Strathclyde's many research active faculties: Engineering, Science, Humanities, Arts & Social Sciences and Strathclyde Business School.

Explore all Strathclyde Open Access research outputs...

On 132-representable graphs

Gao, Alice L.L. and Kitaev, Sergey and Zhang, Philip B. (2017) On 132-representable graphs. Australasian Journal of Combinatorics, 69 (1). pp. 105-118. ISSN 1034-4942 (In Press)

[img]
Preview
Text (Gao-etal-AJC2017-On-132-representable-graphs)
Gao_etal_AJC2017_On_132_representable_graphs.pdf - Accepted Author Manuscript

Download (120kB) | Preview

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.