完全二部图的Gallai猜想  

Gallai's conjecture for complete bipartite graphs

作　　者：耿显亚 柴惠 GENG Xianya;CHAI Hui(School of Mathematics and Big Data,Anhui University of Science&Technology,Huainan 232000,Anhui,China)

机构地区：[1]安徽理工大学数学与大数据学院,安徽淮南232000

出　　处：《运筹学学报(中英文)》2025年第1期232-238,共7页Operations Research Transactions

基　　金：国家自然科学基金(No.12171190);安徽省自然科学基金(No.2008085MA01)。

摘　　要：设G是具有n个顶点的简单连通图。Gallai于1966年提出关于图的路分解猜想:每个n阶简单连通图G都可以被分解为至多[n/2]条路。在本文中,我们利用算法证明了Gallai猜想对于完全二部图Kn_(1),n_(2)成立,这里1≤n_(2)<n_(1)且n_(1)是奇数。结合Constantinou和Ellinas(2018)的结果,我们证明了对于任意的完全二部图,Gallai猜想成立。Let G be a connected simple graph on n vertices.The Gallai's conjecture(1966)asserts that every simple connected graph G on n vertices can be decomposed into at most[n/2]paths.In this paper,we prove that Gallai's conjecture is true for each complete bipartite graph K_(n_(1),n_(2)),where 1≤n_(2)<n_(1)and n_(1)is odd.Together with the conclusions of[1],we show that Gallai's conjecture holds for all complete bipartite graphs.

关 键 词：完全二部图 路分解 Gallai猜想 

分 类 号：O221.2[理学—运筹学与控制论]