Ore-type degree conditions for disjoint path covers in simple graphs

详细信息    查看全文

• 作者：Hyeong-Seok Lim^a ; ^{hslim@chonnam.ac.kr" class="auth_mail" title="E-mail the corresponding author} ; Hee-Chul Kim^b ; ^{hckim@hufs.ac.kr" class="auth_mail" title="E-mail the corresponding author} ; Jung-Heum Park^c ; ^{j.h.park@catholic.ac.kr" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Ore&rsquo ; s theorem ; Degree condition ; Disjoint path cover ; Path partition ; Hamiltonian-connected
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 February 2016
• 年：2016
• 卷：339
• 期：2
• 页码：770-779
• 全文大小：684 K

文摘

A many-to-many  k$k$-disjoint path cover   of a graph joining two disjoint vertex subsets S$S$ and T$T$ of equal size k$k$ is a set of k$k$ vertex-disjoint paths between S$S$ and T$T$ that altogether cover every vertex of the graph. It is classified as paired   if each source in S$S$ is required to be paired with a specific sink in T$T$, or unpaired   otherwise. In this paper, we develop Ore-type sufficient conditions for the existence of many-to-many k$k$-disjoint path covers joining arbitrary vertex subsets S$S$ and T$T$. Also, an Ore-type degree condition is established for the one-to-many k$k$-disjoint path cover, a variant derived by allowing to share a single source. The bounds on the degree sum are all best possible.