Picture of automobile manufacturing plant

Driving innovations in manufacturing: Open Access research from DMEM

Strathprints makes available Open Access scholarly outputs by Strathclyde's Department of Design, Manufacture & Engineering Management (DMEM).

Centred on the vision of 'Delivering Total Engineering', DMEM is a centre for excellence in the processes, systems and technologies needed to support and enable engineering from concept to remanufacture. From user-centred design to sustainable design, from manufacturing operations to remanufacturing, from advanced materials research to systems engineering.

Explore Open Access research by DMEM...

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

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


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.