论文标题
关于简化de bruijn图的单词代表性
On word-representability of simplified de Bruijn graphs
论文作者
论文摘要
如果在字母$ v $上存在一个单词$ w $，则图$ g =（v，e）$是可以说明的。单词代表图概括了几个重要类的图形，例如$ 3 $可油的图，圆形图和可比性图。文献中有一系列研究，专门针对单词代表的图。在本文中，我们研究了简化的de bruijn图的单词表示性。简化的de bruijn Graph $ s（n，k）$是一个简单的图形，它是从de bruijn Graph $ b（n，k）$中获得的，通过删除方向和循环并用单个边缘替换一对顶点之间的多个边缘。 de bruijn图是在单词上，特别是在基因组组装中发现了许多应用的单词中的关键对象。我们表明，对于任何$ n \ geq 1 $，二进制简化的de bruijn图（即\ $ s（n，2）$）都是单词代表的，而$ s（2，k）$和$ s（3，k）$对于$ k \ egeq 3 $不可证明。我们猜想所有简化的de bruijn图$ s（n，k）$对于$ n \ geq 4 $和$ k \ geq 3 $的非字重点。
A graph $G=(V,E)$ is word-representable if there exists a word $w$ over the alphabet $V$ such that letters $x$ and $y$ alternate in $w$ if and only if $xy\in E$. Word-representable graphs generalize several important classes of graphs such as $3$-colorable graphs, circle graphs, and comparability graphs. There is a long line of research in the literature dedicated to word-representable graphs. In this paper, we study word-representability of simplified de Bruijn graphs. The simplified de Bruijn graph $S(n,k)$ is a simple graph obtained from the de Bruijn graph $B(n,k)$ by removing orientations and loops and replacing multiple edges between a pair of vertices by a single edge. De Bruijn graphs are a key object in combinatorics on words that found numerous applications, in particular, in genome assembly. We show that binary simplified de Bruijn graphs (i.e.\ $S(n,2)$) are word-representable for any $n\geq 1$, while $S(2,k)$ and $S(3,k)$ are non-word-representable for $k\geq 3$. We conjecture that all simplified de Bruijn graphs $S(n,k)$ are non-word-rerpesentable for $n\geq 4$ and $k\geq 3$.
