AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home AIMS Mathematics Article
PDF (273.4 KB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Research Article | Open Access

Gallai's path decomposition conjecture for block graphs

Xiaohong Chen, Baoyindureng Wu( )
College of Mathematics and System Science, Xinjiang University, Urumqi, Xinjiang 830046, China
Show Author Information

Abstract

Let G be a graph of order n. A path decomposition 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 ) ≤ ⌈ n 2 ⌉. In this paper, we prove that the above conjecture holds for all block graphs.

Keywords

path decompositionGallai's conjectureblock graphscut vertexend block
CLC number: 05C38, 05C70

References

【1】
【1】
 
 
Crossref Google Scholar
AIMS Mathematics
Volume 10 Issue 1,
January 2025
Pages 1438-1447
DOI: 10.3934/math.2025066

{{item.num}}

Comments on this article

Go to comment

< Back to all reports

Review Status: {{reviewData.commendedNum}} Commended , {{reviewData.revisionRequiredNum}} Revision Required , {{reviewData.notCommendedNum}} Not Commended Under Peer Review

Review Comment

Cite this Report
Close
Close
Cite this article:
Chen X, Wu B. Gallai's path decomposition conjecture for block graphs. AIMS Mathematics, 2025, 10(1): 1438-1447. https://doi.org/10.3934/math.2025066

7

Views

0

Downloads

0

Crossref

0

Web of Science

0

Scopus
Received: 28 August 2024
Revised: 26 December 2024
Accepted: 07 January 2025
Published: 15 January 2025
©2025 the Author(s), licensee AIMS Press.

This is an open access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0)