Gallai's path decomposition conjecture for block graphs

Xiaohong Chen; Baoyindureng Wu; Xiaohong Chen; Baoyindureng Wu

doi:10.3934/math.2025066

AIMS Mathematics

2025, Volume 10, Issue 1: 1438-1447. doi: 10.3934/math.2025066

Previous Article Next Article

Research article Topical Sections

Gallai's path decomposition conjecture for block graphs

Xiaohong Chen ,
Baoyindureng Wu ^,

College of Mathematics and System Science, Xinjiang University, Urumqi, Xinjiang 830046, China

Received: 28 August 2024 Revised: 26 December 2024 Accepted: 07 January 2025 Published: 22 January 2025
MSC : 05C38, 05C70

Let $ G $ be a graph of order $ n $. A path decomposition $ \mathcal{P} $ of $ G $ is a collection of edge-disjoint paths that covers all the edges of $ G $. Let $ p(G) $ denote the minimum number of paths needed in a path decomposition of $ G $. Gallai conjectured that if $ G $ is connected, then $ p(G)\leq \lceil\frac{n}{2}\rceil $. In this paper, we prove that the above conjecture holds for all block graphs.
- path decomposition,
- Gallai's conjecture,
- block graphs,
- cut vertex,
- end block
Citation: Xiaohong Chen, Baoyindureng Wu. Gallai's path decomposition conjecture for block graphs[J]. AIMS Mathematics, 2025, 10(1): 1438-1447. doi: 10.3934/math.2025066

Related Papers:

Abstract

Let $ G $ be a graph of order $ n $. A path decomposition $ \mathcal{P} $ of $ G $ is a collection of edge-disjoint paths that covers all the edges of $ G $. Let $ p(G) $ denote the minimum number of paths needed in a path decomposition of $ G $. Gallai conjectured that if $ G $ is connected, then $ p(G)\leq \lceil\frac{n}{2}\rceil $. In this paper, we prove that the above conjecture holds for all block graphs.

References

[1]	K. J. Balodis, M. E. Kroeker, L. Mol, O. R. Oellermann, On the mean order of connected induced subgraphs of block graphs, Australas. J. Combin., 76 (2020), 128–148.
[2]	A. Behtoei, M. Jannesari, B. Taeri, A characterization of block graphs, Discrete Appl. Math., 158 (2010), 219–221. https://doi.org/10.1016/j.dam.2009.09.024 doi: 10.1016/j.dam.2009.09.024
[3]	M. Bonamy, T. J. Perrett, Gallai's path decomposition conjecture for graphs of small maximum degree, Discrete Math., 342 (2019), 1293–1299. https://doi.org/10.1016/j.disc.2019.01.005 doi: 10.1016/j.disc.2019.01.005
[4]	J. A. Bondy, U. S. R. Murty, Graph theory, London: Springer, 2008.
[5]	F. Botler, A. Jiménez, On path decompositions of $2k$-regular graphs, Discrete Math., 340 (2017), 1405–1411. https://doi.org/10.1016/j.disc.2016.09.029 doi: 10.1016/j.disc.2016.09.029
[6]	F. Botler, A. Jiménez, M. Sambinelli, Gallai's path decomposition conjecture for triangle-free planar graphs, Discrete Math., 342 (2019), 1403–1414. https://doi.org/10.1016/j.disc.2019.01.020 doi: 10.1016/j.disc.2019.01.020
[7]	F. Botler, M. Sambinelli, Towards Gallai's path decomposition conjecture, J. Graph Theor., 97 (2020), 161–184. https://doi.org/10.1002/jgt.22647 doi: 10.1002/jgt.22647
[8]	F. Botler, M. Sambinelli, R. S. Coelho, O. Lee, Gallai's path decomposition conjecture for graphs with treewidth at most 3, J. Graph Theor., 93 (2020), 328–349. https://doi.org/10.1002/jgt.22489 doi: 10.1002/jgt.22489
[9]	Y. Chu, G. Fan, Q. Liu, On Gallai's conjecture for graphs with maximum degree 6, Discrete Math., 344 (2021), 112212. https://doi.org/10.1016/j.disc.2020.112212 doi: 10.1016/j.disc.2020.112212
[10]	Y. Chu, G. Fan, C. Zhou, Path decomposition of triangle-free graphs, Discrete Math., 345 (2022), 112866. https://doi.org/10.1016/j.disc.2022.112866 doi: 10.1016/j.disc.2022.112866
[11]	N. Dean, M. Kouider, Gallai's conjecture for disconnected graphs, Discrete Math., 213 (2000), 43–54. https://doi.org/10.1016/S0012-365X(99)00167-3 doi: 10.1016/S0012-365X(99)00167-3
[12]	A. Donald, An upper bound for the path number of a graph, J. Graph Theor., 4 (1980), 189–201. https://doi.org/10.1002/jgt.3190040207 doi: 10.1002/jgt.3190040207
[13]	G. Fan, Path decompositions and Gallai's conjecture, J. Comb. Theory B, 93 (2005), 117–125. https://doi.org/10.1016/j.jctb.2004.09.008 doi: 10.1016/j.jctb.2004.09.008
[14]	X. Geng, M. Fang, D. Li, Gallai's conjecture for outerplanar graphs, J. Interdiscip. Math., 18 (2015), 593–598. https://doi.org/10.1080/09720502.2014.1001570 doi: 10.1080/09720502.2014.1001570
[15]	P. Harding, S. McGuinness, Gallai's conjecture for graphs of girth at least four, J. Graph Theor., 75 (2014), 256–274. https://doi.org/10.1002/jgt.21735 doi: 10.1002/jgt.21735
[16]	N. Immorlica, M. Mahdian, V. S. Mirrokni, Cycle cover with short cycles, In: STACS 2005, Berlin, Heidelberg: Springer, 2005,641–653. https://doi.org/10.1007/978-3-540-31856-9_53
[17]	A. Jiménez, Y. Wakabayashi, On path-cycle decompositions of triangle-free graphs, Discrete Mathematics & Theoretical Computer Science, 19 (2017), 7. https://doi.org/10.23638/DMTCS-19-3-7 doi: 10.23638/DMTCS-19-3-7
[18]	V. B. Le, N. N. Tuy, The square of a block graph, Discrete Math., 310 (2010), 734–741. https://doi.org/10.1016/j.disc.2009.09.004 doi: 10.1016/j.disc.2009.09.004
[19]	L. Lovász, On covering of graphs, In: Theory of graphs, New York: Academic Press, 1968,231–236.
[20]	D. Pradhan, A. Jha, On computing a minimum secure dominating set in block graphs, J. Comb. Optim., 35 (2018), 613–631. https://doi.org/10.1007/s10878-017-0197-y doi: 10.1007/s10878-017-0197-y
[21]	L. Pyber, Covering the edges of a connected graph by paths, J. Comb. Theory B, 66 (1996), 152–159. https://doi.org/10.1006/jctb.1996.0012 doi: 10.1006/jctb.1996.0012
[22]	C. Wang, L. Chen, C. Lu, $k$-Power domination in block graphs, J. Comb. Optim., 31 (2016), 865–873. http://doi.org/10.1007/s10878-014-9795-0 doi: 10.1007/s10878-014-9795-0

Reader Comments

Your name:*

Email:*
© 2025 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)