Picture of sea vessel plough through rough maritime conditions

Innovations in marine technology, pioneered through Open Access research...

Strathprints makes available scholarly Open Access content by researchers in the Department of Naval Architecture, Ocean & Marine Engineering based within the Faculty of Engineering.

Research here explores the potential of marine renewables, such as offshore wind, current and wave energy devices to promote the delivery of diverse energy sources. Expertise in offshore hydrodynamics in offshore structures also informs innovations within the oil and gas industries. But as a world-leading centre of marine technology, the Department is recognised as the leading authority in all areas related to maritime safety, such as resilience engineering, collision avoidance and risk-based ship design. Techniques to support sustainability vessel life cycle management is a key research focus.

Explore the Open Access research of the Department of Naval Architecture, Ocean & Marine Engineering. 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.