Picture of person typing on laptop with programming code visible on the laptop screen

World class computing and information science research at Strathclyde...

The Strathprints institutional repository is a digital archive of University of Strathclyde's Open Access research outputs. Strathprints provides access to thousands of Open Access research papers by University of Strathclyde researchers, including by researchers from the Department of Computer & Information Sciences involved in mathematically structured programming, similarity and metric search, computer security, software systems, combinatronics and digital health.

The Department also includes the iSchool Research Group, which performs leading research into socio-technical phenomena and topics such as information retrieval and information seeking behaviour.

Explore

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.