Graphs capturing alternations in words

Halldorsson, Magnus and Kitaev, Sergey and Pyatkin, Artem; Gao, Yuan and Lu, Hanlin and Seki, Shinnosuke and Yu, Sheng, eds. (2010) Graphs capturing alternations in words. In: Developments in Language Theory. Lecture Notes in Computer Science . Springer-Verlag Berlin, CAN, pp. 436-437. ISBN 978-3-642-14454-7 (

Full text not available in this repository.Request a copy


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].