设G是具有n个顶点的简单连通图。Gallai于1966年提出关于图的路分解猜想:每个n阶简单连通图G都可以被分解为至多[n/2]条路。在本文中,我们利用算法证明了Gallai猜想对于完全二部图K_(n_1,n_2)成立,这里1≤n_2<n_1且n_1是奇数。结合文献[1]的结果,我们证明了对于任意的完全二部图,Gallai猜想成立。
科研之友
微信
新浪微博
Facebook
分享链接
