2024/09/10 by Sahu, Akankshya, Padinhatteeri, Sajith
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2409.06298
openalex publication_date 2024/09/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Gallai's path decomposition conjecture states that for a connected graph G on n vertices, there exists a path decomposition of size \lceil (n)/(2) \rceil. The Levi graph of order one, denoted by L1(m,k), is a bipartite graph with vertex partition (A,B), where A is the collection of all (k-1)-element subsets of [m], and B is the collection of all k-element subsets of [m]. In this graph, a (k-1)-element subset is adjacent to a k-element subset if and only if it is properly contained within the k-element subset. The path number of a graph G is the minimum size of its path decomposition. Gallai's conjecture can be seen as a conjecture on the upper bound of the path number of a connected graph. In this work, we prove the conjecture for L1(m,k) for all m ≥ 2 and 2 ≤ k ≤ m. Moreover, we determine the path number of L1(m,2) for all m.