完全二部图的Gallai猜想

doi:10.15960/j.cnki.issn.1007-6093.2025.01.020

运筹学学报（中英文） ›› 2025, Vol. 29 ›› Issue (1): 232-238.doi: 10.15960/j.cnki.issn.1007-6093.2025.01.020

• • 上一篇

完全二部图的Gallai猜想

耿显亚¹^,*(), 柴惠¹

1. 安徽理工大学数学与大数据学院, 安徽淮南 232000

收稿日期:2021-09-27 出版日期:2025-03-15 发布日期:2025-03-08
通讯作者: 耿显亚 E-mail:gengxianya@sina.com
基金资助:
国家自然科学基金(12171190);安徽省自然科学基金(2008085MA01)

Gallai's conjecture for complete bipartite graphs

Xianya GENG¹^,*(), Hui CHAI¹

1. School of Mathematics and Big Data, Anhui University of Science & Technology, Huainan 232000, Anhui, China

Received:2021-09-27 Online:2025-03-15 Published:2025-03-08
Contact: Xianya GENG E-mail:gengxianya@sina.com

摘要/Abstract

摘要：

设$G$是具有$n$个顶点的简单连通图。Gallai于1966年提出关于图的路分解猜想: 每个$n$阶简单连通图$G$都可以被分解为至多$\left\lceil\frac{n}{2}\right\rceil$条路。在本文中, 我们利用算法证明了Gallai猜想对于完全二部图$K_{n_1, n_2}$成立, 这里1≤n₂ < n₁且n₁是奇数。结合Constantinou和Ellinas (2018)的结果, 我们证明了对于任意的完全二部图, Gallai猜想成立。

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

Abstract:

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 $\left\lceil\frac{n}{2}\right\rceil$ 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₂ < n₁ and n₁ is odd. Together with the conclusions of [1], we show that Gallai's conjecture holds for all complete bipartite graphs.

Key words: complete bipartite graphs, path decomposition, Gallai's conjecture

中图分类号:

O221.2

耿显亚, 柴惠. 完全二部图的Gallai猜想[J]. 运筹学学报（中英文）, 2025, 29(1): 232-238.

Xianya GENG, Hui CHAI. Gallai's conjecture for complete bipartite graphs[J]. Operations Research Transactions, 2025, 29(1): 232-238.

图/表 1

参考文献 16

1	Lovász L. On covering of graphs [M]//Erdos P, Katona G (eds). Theory of Graphs, New York: Academin Press, 1968: 231-236.
2	Fan G H . Path decompositions and Gallai's conjecture[J]. Journal of Combinatorial Theory, Series B, 2005, 93 (2): 117- 125. doi: 10.1016/j.jctb.2004.09.008
3	Favaron O , Kouider M . Path partitions and cycle partitions of Eulerian graphs of maximum degree 4[J]. Studia Scientiarum Mathematicarum Hungarica, 1988, 1, 237- 244.
4	Geng X Y , Fang M L , Li D Q . Gallai's conjecture for outerplanar graphs[J]. Journal of Interdisciplinary Mathematics, 2015, 18 (5): 593- 598. doi: 10.1080/09720502.2014.1001570
5	Alspach B . The wonderful Walecki construction[J]. Bulletin of the Institute of Combinatorics and Its Applications, 2008, 52, 7- 20.
6	Bryant D . Packing paths in complete graphs[J]. Journal of Combinatorial Theory, 2010, 100 (2): 206- 215. doi: 10.1016/j.jctb.2009.08.004
7	Fu C M , Huang K C , Mishima M . Decomposition of complete bipartite graphs into cycles of distinct even lengths[J]. Graphs and Combinatorics, 2016, 32 (4): 1397- 1413. doi: 10.1007/s00373-015-1664-9
8	Parker C. Complete bipartite graph path decompositions [D]. Alabama: Auburn University, 1998.
9	Zhai M Q , Lu C H . Path decomposition of graphs with given path length[J]. Acta Mathematicae Applicatae Sinica, 2006, 22 (4): 633- 638. doi: 10.1007/s10255-006-0337-0
10	Haggkvist R , Johansson R . A note on edge-decompositions of planar graphs[J]. Discrete Mathematics, 2004, 283, 263- 266. doi: 10.1016/j.disc.2003.11.017
11	Thomassen C . Edge-decompositions of highly connected graphs into paths[J]. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 2008, 78 (1): 17- 26. doi: 10.1007/s12188-008-0002-z
12	Heinrich K . Path-decompositions[J]. Matematiche, 1992, 47 (2): 241- 258.
13	Tarsi M . Decomposition of a complete multigraph into simple paths: nonbalanced handcuffed designs[J]. Journal of Combinatorial Theory, Series A, 1983, 34 (1): 60- 70. doi: 10.1016/0097-3165(83)90040-7
14	Pyber L . Covering the edges of a connected graph by paths[J]. Journal of Combinatorial Theory, Series B, 1996, 66 (1): 152- 159. doi: 10.1006/jctb.1996.0012
15	Donald A . An upper bound for the path number of a graph[J]. Journal of Graph Theory, 1980, 4 (2): 189- 201. doi: 10.1002/jgt.3190040207
16	Constantinou C K , Ellinas G . Minimal path decomposition of complete bipartite graphs[J]. Journal of Combinatorial Optimization, 2018, 35, 684- 702. doi: 10.1007/s10878-017-0200-7

情况	特点
1	$ n_{1}=n_{2} $且$ n_{1} $为偶数
2	$ n_{1}=n_{2} $且$ n_{1} $为奇数
3	$ 1{\leqslant} n_{2}< n_{1} $且$ n_{1} $为偶数
4	$ 1{\leqslant} n_{2}< n_{1} $且$ n_{1} $为奇数

完全二部图的Gallai猜想

Gallai's conjecture for complete bipartite graphs

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 1

参考文献 16

相关文章 1

编辑推荐

Metrics

本文评价