Gallai's Path Decomposition of Levi Graph

Abstract

Gallai's path decomposition conjecture states that for a connected graph $G$ on $n$ vertices, there exists a path decomposition of size $\lceil \frac{n}{2}\rceil$. The Levi graph of order one, denoted by $L_1(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 $L_1(m,k)$ for all $m\ge 2$ and $2\le k\le m$. Moreover, we determine the path number of $L_1(m,2)$ for all $m$.