On word-representability of simplified de Bruijn graphs Anthony Petyuk

2025-05-02 0 0 414.88KB 11 页 10玖币

侵权投诉

On word-representability of simpliﬁed de Bruijn

graphs

Anthony Petyuk∗

July 13, 2023

Abstract

A graph G= (V, E) is word-representable if there exists a word w

over the alphabet Vsuch that letters xand yalternate in wif and

only if xy ∈E. Word-representable graphs generalize several impor-

tant 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 simpliﬁed de Bruijn

graphs. The simpliﬁed de Bruijn graph S(n, k) is a simple graph ob-

tained 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 as-

sembly. We show that binary simpliﬁed de Bruijn graphs (i.e. S(n, 2))

are word-representable for any n≥1, while S(2, k) and S(3, k) are

non-word-representable for k≥3. We conjecture that all simpliﬁed de

Bruijn graphs S(n, k) are non-word-rerpesentable for n≥4 and k≥3.

1 Introduction

1.1 Word-representable graphs and semi-transitive

orientations.

Two letters xand yalternate in a word wif after deleting in wall

letters but the copies of xand ywe either obtain a word xyxy · · · (of

even or odd length) or a word yxyx · · · (of even or odd length). A

graph G= (V, E) is word-representable if there exists a word wover

∗College of Letters and Science, University of California, Berkeley, California, USA.

Email: anthony.petyuk@berkeley.edu

arXiv:2210.14762v2 [math.CO] 12 Jul 2023

the alphabet Vsuch that letters xand yalternate in wif and only if

xy ∈E.

There is a long line of research papers dedicated to the theory of

word-representable graphs (e.g. see [4, 5] and references therein). The

motivation to study these graphs is their relevance to algebra, graph

theory, computer science, combinatorics on words, and scheduling [5].

In particular, word-representable graphs generalize several important

classes of graphs (e.g. circle graphs, 3-colorable graphs and compa-

rability graphs). By [4, 5], the minimal (by the number of vertices)

non-word-representable graph is the wheel graph W5on six vertices

(which is obtained by adding to the cycle graph C5an all-adjacent

vertex; see Figure 1).

An orientation of a graph is semi-transitive if it is acyclic, and for

any directed path v0→v1→ · · · → vkeither there is no arc between

v0and vk, or vi→vjis an arc for all 0 ≤i<j≤k. An undirected

graph is semi-transitive if it admits a semi-transitive orientation. A

key result in the theory of word-representable graphs is the following

theorem.

Theorem 1 ([3]).A graph is word-representable if and only if it is

semi-transitive.

As an immediate corollary to Theorem 1 we have the following

result.

Theorem 2 ([3]).Any 3-colorable graph is word-representable.

Finally, we note the handy software to work with word-representable

graphs [2, 8].

1.2 Simpliﬁed de Bruijn graphs.

Let A={0,1, . . . , k −1}be a k-letter alphabet and Anbe the set of

all words over Aof length n. A de Bruijn graph B(n, k) consists of kn

vertices labeled by words in Anand its directed edges are x1x2· · · xn→

x2· · · xnxn+1 where xi∈Afor i∈ {1,2, . . . , n + 1}. De Bruijn graphs

are an important structure in combinatorics on words that found wide

applications, in particular, in genome assembly [1].

The simpliﬁed de Bruijn graph S(n, k) is a simple graph obtained

from B(n, k) by removing orientations and loops and replacing mul-

tiple edges between a pair of vertices by a single edge. To our best

knowledge, the notion of a simpliﬁed de Bruijn graph is introduced in

this paper for the ﬁrst time. We label the edge between x1x2· · · xn

and x2x3· · · xn+1 in S(n, k) by x1x2· · · xn+1.

1.3 Results in this paper.

In Section 2 we show that binary simpliﬁed de Bruijn graphs are word-

representable. In Section 3 we show that S(2, k) and S(3, k) are non-

word-representable for k≥3. In Section 4 we state a conjecture on full

classiﬁcation of word-representable simpliﬁed de Bruijn graphs along

with an open problem.

2 Word-representability of S(n, 2)

Let xk=x...x

| {z }

ktimes

and ¯

0 = 1 and ¯

1 = 0.

Theorem 3. S(n, 2) is word-representable for any n≥1.

Proof. We will show that S(n, 2) is 3-colorable so that the desired

result will follow from Theorem 2. Clearly, S(1,2) is 3-colorable, so

that we can assume that n≥2.

All vertices in S(n, 2) can be subdivided into the following three

disjoint groups: vertices ending with ¯xx2kfor k≥1 (where the ¯xcan

be absent), those ending with 102k+1 for k≥0 (where the 1 can be

absent), and those ending with 012k+1 for k≥0 (where the 0 can be

absent). We colour the vertices in these groups Red, Blue and Green,

respectively.

Since S(n, 2) has no loops, its edges correspond to the following

two types of edges in B(n, 2):

•Edges uv in B(n, 2), where the words corresponding to uand v

end in the same letter. Since one of uor vmust end in an odd

number of repeated letters and the other must end in an even

number of repeated letters, these directed edges correspond to

edges in S(2, k) where the colours of uand vare always diﬀerent.

•Edges uv in B(n, 2), where the words corresponding to uand v

end in diﬀerent letters. The vertex vmust end in one repeated

letter x(an odd number of letters), and umust end in either

an even or an odd number of repeated letters ¯x. These directed

edges also correspond to edges in S(2, k) where the colors of u

and vare always diﬀerent.

Thus, we have constructed a proper 3-colouring of S(2, k).

3 Non-word-representability of S(2, k)and

S(3, k)for k≥3

Theorem 4. S(2, k)is non-word-representable for any k≥3.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Onword-representabilityofsimplifieddeBruijngraphsAnthonyPetyuk∗July13,2023AbstractAgraphG=(V,E)isword-representableifthereexistsawordwoverthealphabetVsuchthatlettersxandyalternateinwifandonlyifxy∈E.Word-representablegraphsgeneralizeseveralimpor-tantclassesofgraphssuchas3-colorablegraphs,circlegraphs...

展开>> 收起<<

On word-representability of simplified de Bruijn graphs Anthony Petyuk.pdf

共11页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

On word-representability of simplified de Bruijn graphs Anthony Petyuk

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: