Picture of wind turbine against blue sky

Open Access research with a real impact...

The Strathprints institutional repository is a digital archive of University of Strathclyde research outputs.

The Energy Systems Research Unit (ESRU) within Strathclyde's Department of Mechanical and Aerospace Engineering is producing Open Access research that can help society deploy and optimise renewable energy systems, such as wind turbine technology.

Explore wind turbine research in Strathprints

Explore all of Strathclyde's Open Access research content

Alternation graphs

Halldorsson, Magnus and Kitaev, Sergey and Pyatkin, Artem (2011) Alternation graphs. In: Graph-theoretic concepts in computer science. Lecture Notes in Computer Science . Springer-Verlag Berlin, Berlin, pp. 191-202. ISBN 9783642258695

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

Abstract

A graph G = (V,E) is an alternation graph 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) ∈ E for each x ≠ y. In this paper we give an effective characterization of alternation graphs in terms of orientations. Namely, we show that a graph is an alternation graph if and only if it admits a semi-transitive orientation defined in the paper. This allows us to prove a number of results about alternation graphs, in particular showing that the recognition problem is in NP, and that alternation graphs include all 3-colorable graphs. We also explore bounds on the size of the word representation of the graph. A graph G is a k-alternation graph if it is represented by a word in which each letter occurs exactly k times; the alternation number of G is the minimum k for which G is a k-alternation graph. We show that the alternation number is always at most n, while there exist graphs for which it is n/2.