Picture child's feet next to pens, pencils and paper

Open Access research that is helping to improve educational outcomes for children

Strathprints makes available scholarly Open Access content by researchers in the School of Education, including those researching educational and social practices in curricular subjects. Research in this area seeks to understand the complex influences that increase curricula capacity and engagement by studying how curriculum practices relate to cultural, intellectual and social practices in and out of schools and nurseries.

Research at the School of Education also spans a number of other areas, including inclusive pedagogy, philosophy of education, health and wellbeing within health-related aspects of education (e.g. physical education and sport pedagogy, autism and technology, counselling education, and pedagogies for mental and emotional health), languages education, and other areas.

Explore Open Access education research. 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.