完全二部图的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.

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.ort.shu.edu.cn/EN/10.15960/j.cnki.issn.1007-6093.2025.01.020

https://www.ort.shu.edu.cn/EN/Y2025/V29/I1/232

Figures/Tables 1

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]	WANG Xiangfeng, ZENG Shangzhi, ZHANG Jin, ZHOU Jinchuan. Proximal-based methods can guarantee blunt local minimizer for nonconvex nonsmooth optimization problem [J]. Operations Research Transactions, 2026, 30(2): 1-23.
[2]	MEN Yanchao, LI Xudong. Fast algorithm for OWL1 norm constrained regression model [J]. Operations Research Transactions, 2026, 30(2): 24-44.
[3]	ZENG Jing, XIANG Yao, ZHANG Wenyan. The well-posedness of traffic equilibrium problems [J]. Operations Research Transactions, 2026, 30(2): 58-68.
[4]	WANG Feng, HANG Bo, HUANG Jinzhou, XU Degang, ZHANG Zeyu, LIU Jiamou. Research of touring route planning based on spatio-temporal awareness [J]. Operations Research Transactions, 2026, 30(2): 69-78.
[5]	WU Xiaoyu, SHAO Hu, LIU Pengjie, ZHOU Jincheng. Two RMIL-type conjugate gradient methods with sufficient descent property and applications in image restoration [J]. Operations Research Transactions, 2026, 30(2): 79-92.
[6]	CUI Hengxin, JIANG Fan. Inexact proximal point algorithms and projection methods for monotone variational inequalities [J]. Operations Research Transactions, 2026, 30(2): 194-208.
[7]	ZHANG Xuefeng, PENG Xiao, CHEN Liangyu, YANG Zhengfeng, ZENG Zhenbing. A review of intelligent branch and bound algorithms for mixed integer linear programming problems [J]. Operations Research Transactions, 2026, 30(2): 237-270.
[8]	WEI Jiazhen, BIAN Wei. A survey on research advances in consensus-based optimization algorithm [J]. Operations Research Transactions, 2026, 30(1): 1-23.
[9]	ZHOU Yunxu, YAO Fanjun, GAO Hongwei. Blockchain empowering the digital transformation: Study on the coordination strategies of supply chain [J]. Operations Research Transactions, 2026, 30(1): 61-74.
[10]	ZHAO Hongxin, KONG Lingchen. Research on diversification portfolio optimization model and method [J]. Operations Research Transactions, 2026, 30(1): 75-92.
[11]	SUN Ke, WANG Jinting, WANG Zhongbin. The economics of waiting-area entertainment [J]. Operations Research Transactions, 2026, 30(1): 93-107.
[12]	XU Ke, JI Lanping, GONG Hua, LIU Peng, SUN Wenjuan. A coordinated multi-agent production and transportation scheduling on parallel machines based on auction algorithm [J]. Operations Research Transactions, 2026, 30(1): 121-136.
[13]	WANG Ziqi, WANG Junlin, XU Zi. A variance reduced gradient descent ascent algorithm for a class of nonconvex-nonconcave minimax problems [J]. Operations Research Transactions, 2026, 30(1): 197-206.
[14]	YANG Jinji, SHEN Chungen, YU Zhensheng. Convergence analysis of an adaptive proximal gradient-subgradient algorithm for square-root-loss regression problems [J]. Operations Research Transactions, 2026, 30(1): 217-234.
[15]	Ruiqing SUN, Rui ZHANG, Yan LAN, Weidong LI. LPT algorithm for early work maximization problem [J]. Operations Research Transactions, 2025, 29(4): 249-254.

Gallai's conjecture for complete bipartite graphs

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 1

Related Articles 15

Recommended Articles

Metrics

Comments