完全二部图的Gallai猜想
Gallai’s conjecture for complete bipartite graphs作者机构:安徽理工大学数学与大数据学院
出 版 物:《运筹学学报》 (Operations Research Transactions)
年 卷 期:2022年
核心收录:
学科分类:07[理学] 070104[理学-应用数学] 0701[理学-数学]
基 金:国家自然科学基金(No.12171190) 安徽省自然科学基金(No.2008085MA01)
摘 要:设G是具有n个顶点的简单连通图。Gallai于1966年提出关于图的路分解猜想:每个n阶简单连通图G都可以被分解为至多[n/2]条路。在本文中,我们利用算法证明了Gallai猜想对于完全二部图K;成立,这里1≤n;n;且n;是奇数。结合文献[1]的结果,我们证明了对于任意的完全二部图,Gallai猜想成立。