Picture of rolled up £5 note

Open Access research that shapes economic thinking...

Strathprints makes available scholarly Open Access content by the Fraser of Allander Institute (FAI), a leading independent economic research unit focused on the Scottish economy and based within the Department of Economics. The FAI focuses on research exploring economics and its role within sustainable growth policy, fiscal analysis, energy and climate change, labour market trends, inclusive growth and wellbeing.

The open content by FAI made available by Strathprints also includes an archive of over 40 years of papers and commentaries published in the Fraser of Allander Economic Commentary, formerly known as the Quarterly Economic Commentary. Founded in 1975, "the Commentary" is the leading publication on the Scottish economy and offers authoritative and independent analysis of the key issues of the day.

Explore Open Access research by FAI or the Department of Economics - or read papers from the Commentary archive [1975-2006] and [2007-2018]. Or explore all of Strathclyde's Open Access research...

Word-representability of line graphs

Kitaev, Sergey and Salimov, Pavel and Severs, Christopher and Ulfarsson, Henning (2011) Word-representability of line graphs. Open Journal of Discrete Mathematics, 1 (2). pp. 96-101. ISSN 2161-7643

Full text not available in this repository. Request a copy from the Strathclyde author

Abstract

A graph G=(V,E) is representable if there exists a word W over the alphabet V such that letters x and y alternate in W if and only if (x ,y) is in E for each x not equal to y . The motivation to study representable graphs came from algebra, but this subject is interesting from graph theoretical, computer science, and combinatorics on words points of view. In this paper, we prove that for n greater than 3, the line graph of an n-wheel is non-representable. This not only provides a new construction of non-repre- sentable graphs, but also answers an open question on representability of the line graph of the 5-wheel, the minimal non-representable graph. Moreover, we show that for n greater than 4, the line graph of the complete graph is also non-representable. We then use these facts to prove that given a graph G which is not a cycle, a path or a claw graph, the graph obtained by taking the line graph of G k-times is guaranteed to be non-representable for k greater than 3.