Content deleted Content added
m JzG moved page Word-representable graph to Draft:Word-representable graph without leaving a redirect: Undersourced, incubate in draftspace. Neologism coined by author of the article. WP:SYN. (via script) |
AFC draft (via script) |
||
Line 1:
{{AFC submission|t||ts=20200205092430|u=S. Kitaev|ns=118|demo=}}
<!-- Note: The following pages were redirects to [[Word-representable_graph]] before draftification:
*[[Draft:Word-representable graphs]]
*[[Word-representable graphs]]
-->
In [[graph theory]], a graph ''G'' = (''V'',''E'') is '''word-representable''' iff there exists a word ''w'' over the alphabet ''V'' such that letters ''a'' and ''b'' alternate in ''w'' if and only if the edge ''ab'' is in ''E''. Letters ''a'' and ''b'' '''alternate''' in ''w'' if after removing from ''w'' all letters but the copies of ''a'' and ''b'' we either obtain a word ''abab''... or a word ''baba''.... In this context, we say that [[W|''w'']] is ''G''<nowiki/>'s '''word-representant''', or that ''w'' '''represents''' ''G''. For example, the [[cycle graph]] labeled by ''x'', ''y'', ''z'' and ''s'' in clock-wise direction is word-representable because it can be represented by ''szxsyxzy''. The smallest (by the number of vertices) non-word-representable graph is the [[wheel graph]] ''W''<sub>5</sub>, which is the only non-word-representable graph on 6 vertices.
Line 153 ⟶ 159:
{{reflist}}
[[:Category:Graph families]]
| |||