Optimal path and cycle decompositions of dense quasirandom graphs

详细信息查看全文

作者：Stefan Glock¹ ; ^{sxg426@bham.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Daniela Kü ; hn ^{d.kuhn@bham.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Deryk Osthus ^{d.osthus@bham.ac.uk" class="auth_mail" title="E-mail the corresponding author}
关键词：cycle decomposition ; path decomposition ; linear arboricity ; overfull subgraph conjecture
刊名：Electronic Notes in Discrete Mathematics
出版年：2015
出版时间：November 2015
年：2015
卷：49
期：Complete
页码：65-72
全文大小：186 K

文摘

Motivated by longstanding conjectures regarding decompositions of graphs into paths and cycles, we prove the following optimal decomposition results for random graphs. Let od=retrieve&_eid=1-s2.0-S1571065315000578&_mathId=si1.gif&_user=111111111&_pii=S1571065315000578&_rdoc=1&_issn=15710653&md5=cacadc9be951d835597cb5d956810655" title="Click to view the MathML source">0<p<1ode">

0 < p < 1

be constant and let od=retrieve&_eid=1-s2.0-S1571065315000578&_mathId=si2.gif&_user=111111111&_pii=S1571065315000578&_rdoc=1&_issn=15710653&md5=751747cbced6a2e00355101ba35d7505" title="Click to view the MathML source">G∼G_n,pode">

G \sim G_{n, p}

. Let odd(G) be the number of odd degree vertices in G. Then a.a.s. the following hold:

(i): G can be decomposed into od=retrieve&_eid=1-s2.0-S1571065315000578&_mathId=si3.gif&_user=111111111&_pii=S1571065315000578&_rdoc=1&_issn=15710653&md5=b02588354e248f0322394d945d8a0816" title="Click to view the MathML source">⌊Δ(G)/2⌋ode"> $⌊ Δ (G) / 2 ⌋$ cycles and a matching of size od=retrieve&_eid=1-s2.0-S1571065315000578&_mathId=si4.gif&_user=111111111&_pii=S1571065315000578&_rdoc=1&_issn=15710653&md5=b5b5d2da5fe039ff0fd4596735a190a8" title="Click to view the MathML source">odd(G)/2ode"> $odd (G) / 2$ .
(ii): G can be decomposed into od=retrieve&_eid=1-s2.0-S1571065315000578&_mathId=si5.gif&_user=111111111&_pii=S1571065315000578&_rdoc=1&_issn=15710653&md5=c7507cd9b17b626b0f57a68860388296" title="Click to view the MathML source">max⁡{odd(G)/2,⌈Δ(G)/2⌉}ode"> $\max {odd (G) / 2, ⌈ Δ (G) / 2 ⌉}$ paths.
(iii): G can be decomposed into od=retrieve&_eid=1-s2.0-S1571065315000578&_mathId=si6.gif&_user=111111111&_pii=S1571065315000578&_rdoc=1&_issn=15710653&md5=702c290a9d1735c8fdc0ee1c7f35f322" title="Click to view the MathML source">⌈Δ(G)/2⌉ode"> $⌈ Δ (G) / 2 ⌉$ linear forests.

Each of these bounds is best possible. We actually derive (i)–(iii) from ‘quasi-random’ versions of our results. In that context, we also determine the edge chromatic number of a given dense quasirandom graph of even order. For all these results, our main tool is a result on Hamilton decompositions of robust expanders by Kühn and Osthus.

地址：北京市海淀区学院路29号邮编：100083

电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700