Word-representable Graph
In the mathematical field of graph theory, a word-representable graph is a graph (discrete mathematics), graph that can be characterized by a word (or sequence) whose entries alternate in a prescribed way. In particular, if the vertex set of the graph is ''V'', one should be able to choose a word ''w'' over the alphabet ''V'' such that letters ''a'' and ''b'' alternate in ''w'' if and only if the pair ''ab'' is an edge in the graph. (Letters ''a'' and ''b'' alternate in ''w'' if, after removing from ''w'' all letters but the copies of ''a'' and ''b'', one obtains a word ''abab''... or a word ''baba''....) For example, the cycle graph labeled by ''a'', ''b'', ''c'' and ''d'' in clock-wise direction is word-representable because it can be represented by ''abdacdbc'': the pairs ''ab'', ''bc'', ''cd'' and ''ad'' alternate, but the pairs ''ac'' and ''bd'' do not. The word ''w'' is ''G'''s ''word-representant'', and one says that that ''w'' ''represents'' ''G''. The smallest (by the num ...
[...More Info...]       [...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]