完全二部图的Gallai猜想

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

Abstract

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

CLC Number:

O221.2

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

Figures/Tables 1

References 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} $为奇数

[1]	Xihong YAN, Xiaoni TANG. An inertial alternating direction method of multiplier for low rank matrix completion [J]. Operations Research Transactions, 2025, 29(1): 172-184.
[2]	Shipian DU, Manzhan GU. Stochastic scheduling to minimize the expected total number of tardy jobs with machine maintenance activities [J]. Operations Research Transactions, 2025, 29(1): 142-158.
[3]	Na LI, Ran MA, Long LI, Yuzhong ZHANG. Study on the production scheduling of prefabricated components with learning effect [J]. Operations Research Transactions, 2025, 29(1): 19-30.
[4]	Chengwen JIAO. Online scheduling on a single parallel-batch machine with linear lookahead [J]. Operations Research Transactions, 2024, 28(4): 111-116.
[5]	Dayong ZHANG, Honglei WANG. Optimization strategy for preventive maintenance of wind turbines in low wind speed areas based on Markov models [J]. Operations Research Transactions, 2024, 28(3): 108-120.
[6]	Fusheng WANG, Luyu SHI. An accelerated proximal stochastic gradient method with variance reduction based on Polyak step size [J]. Operations Research Transactions, 2024, 28(2): 131-142.
[7]	Minglu YE, Ming HUANG. An inertial projection algorithm for nonmonotone continuous variational inequalities [J]. Operations Research Transactions, 2024, 28(2): 81-92.
[8]	Juannian XU, Ran MA, Wenwen HAN, Yuzhong ZHANG. Single-machine online scheduling to minimize maximum weighted completion time with limited weights [J]. Operations Research Transactions, 2024, 28(2): 71-80.
[9]	Jiaqi ZHANG, Jueyou LI. A class of differential privacy stochastic gradient descent algorithm with adaptive gradient clipping [J]. Operations Research Transactions, 2024, 28(2): 47-57.
[10]	Yukun CHENG, Xin HAN, Xiuyang CHEN, Zhao ZHANG. Survey on several combinatorial optimization games on networks [J]. Operations Research Transactions, 2024, 28(2): 1-29.
[11]	Xuezheng LYU, Mengyu MA. The distance spectra of chain graphs [J]. Operations Research Transactions, 2024, 28(1): 112-120.
[12]	Fusheng BAI, Mi LAN. An adaptive surrogate optimization method for expensive black-box problems with hidden constraints [J]. Operations Research Transactions, 2024, 28(1): 89-100.
[13]	Yinghan LI, Xiaojiao TONG, Liu YANG. The study of distributionally robust reward-risk optimization models with moment-based ambiguity set [J]. Operations Research Transactions, 2024, 28(1): 77-88.
[14]	Yang XU, Junlin WANG, Zi XU. A mirror descent gradient ascent algorithm for one side relatively smooth nonconvex-concave minimax optimization problems [J]. Operations Research Transactions, 2024, 28(1): 18-28.
[15]	Xinqing MENG, Wenxing ZAHNG. An accelerated method for solving a class of linear equality constrained convex optimization [J]. Operations Research Transactions, 2024, 28(1): 1-17.

Gallai's conjecture for complete bipartite graphs

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 1

References 16

Related Articles 15

Recommended Articles

Metrics

Comments