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

Representing graphs via pattern avoiding words

Jones, Miles and Kitaev, Sergey and Pyatkin, Artem and Remmel, Jeffrey (2015) Representing graphs via pattern avoiding words. The Electronic Journal of Combinatorics, 22 (2). ISSN 1077-8926

[img]
Preview
Text (Jones-etal-EJOC-2015-Representing-graphs-via-pattern-avoiding-words)
Jones_etal_EJOC_2015_Representing_graphs_via_pattern_avoiding_words.pdf - Accepted Author Manuscript

Download (273kB) | Preview

Abstract

The notion of a word-representable graph has been studied in a series of papers in the literature. 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 . If V = {1,...,n}, this is equivalent to saying that G is word-representable if for all x,y ϵ {1,…,n}, xy ϵ E if and only if the subword w {x,y} of w consisting of all occurrences of x or y in w has no consecutive occurrence of the pattern 11. In this paper, we introduce the study of u -representable graphs for any word u ϵ {1, 2}*. A graph G is u -representable if and only if there is a vertex-labeled version of G, G = ( {1,…,n},E ), and a word w ϵ {1,…,n}* such that for all x,y ϵ {1,…,n}, xy ϵ E if and only if w {x,y} has no consecutive occurrence of the pattern u . Thus, word-representable graphs are just 11-representable graphs. We show that for any k > 3, every finite graph G is 1 k - representable. This contrasts with the fact that not all graphs are 11-representable graphs. The main focus of the paper is the study of 12-representable graphs. In particular, we classify the 12-representable trees. We show that any 12-representable graph is a comparability graph and the class of 12-representable graphs include the classes of co-interval graphs and permutation graphs. We also state a number of facts on 12-representation of induced subgraphs of a grid graph.