Picture of smart phone in human hand

World leading smartphone and mobile technology 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 Strathclyde researchers from the Department of Computer & Information Sciences involved in researching exciting new applications for mobile and smartphone technology. But the transformative application of mobile technologies is also the focus of research within disciplines as diverse as Electronic & Electrical Engineering, Marketing, Human Resource Management and Biomedical Enginering, among others.

Explore Strathclyde's Open Access research on smartphone technology now...

Existence of μ-representation of graphs

Kitaev, Sergey (2016) Existence of μ-representation of graphs. Journal of Graph Theory. ISSN 1097-0118 (In Press)

[img] Text (Kitaev-JGT2016-Existence-of-μ-representation-of-graphs)
Kitaev_JGT2016_Existence_of_representation_of_graphs.pdf - Accepted Author Manuscript
Restricted to Repository staff only until 5 August 2017.

Download (77kB) | Request a copy from the Strathclyde author

Abstract

Recently, Jones et al. introduced the study of μ-representable graphs, where μ is a word over { 1,2} containing at least one 1. The notion of a μ-representable graph is a far-reaching generalization of the notion of a word-representable graph studied in the literature in a series of papers. Jones et al. have shown that any graph is 11⋯1-representable assuming that the number of 1s is at least three, while the class of 12-rerpesentable graphs is properly contained in the class of comparability graphs, which, in turn, is properly contained in the class of word-representable graphs corresponding to 11-representable graphs. Further studies in this direction were conducted by Nabawanda, who has shown, in particular, that the class of 112-representable graphs is not included in the class of word-representable graphs. Jones et al. raised a question on classification of μ-representable graphs at least for small values of μ. In this paper we show that if μ is of length at least 3 then any graph is μ-representable. This rather unexpected result shows that from existence of representation point of view there are only two interesting non-equivalent cases in the theory of μ-representable graphs, namely, those of μ=11 and μ=12.