2023/10/17 by Chen, Xiaohong, Baoyindureng Wu, Wu, Baoyindureng
Computer Science · Mathematics · #05C38 #05C70 #05C76 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2310.11189
openalex publication_date 2023/10/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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)≤ \lceil(n)/(2)\rceil. Let no(G) to denote the number of vertices with odd degree in G. Lovász proved that if G is a connected graph with all vertices having degree odd, i.e. no(G)=n, then p(G)=\frac n 2. In this paper, we prove that if G is a connected graph of order m≥ 2 with p(G)=(no(G))/(2) and H is a connected graph of order n, then p(G\Box H)≤(mn)/(2). Furthermore, we prove that p(G)=(no(G))/(2), if one of the following is hold: (\romannumeral1) G is a tree; (\romannumeral2) G=Pn\Box T, where n≥ 4 and T is a tree; (\romannumeral3) G=Pn\Box H, where H is an even graph.