Graphs capturing alternations in words

Halldorsson, Magnus and Kitaev, Sergey and Pyatkin, Artem (2010) Graphs capturing alternations in words. In: Developments in Language Theory. Lecture Notes in Computer Science . Springer-Verlag Berlin, pp. 436-437. ISBN 978-3-642-14454-7

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) ∈ E for each x ≠ y. If W is k-uniform (each letter of W occurs exactly k times in it) then G is called k-representable. A graph is representable if and only if it is k-representable for some k [1].