On Gallai's conjecture for path decomposition of graphs
| Autor: | Wu-Hsiung Lin, 林武雄 |
|---|---|
| Rok vydání: | 2003 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 91 Suppose $G=(V,E)$ is a simple, finite, undirected graph. A path decomposition $\Sigma$ for a graph $G$ is a partition of the edge set $E$ into paths. Denote $p(G)$ the minimum number of paths needed for a path decomposition of a graph $G$. Gallai conjectured that $p(G)\leq\lceil\frac{n}{2}\rceil$ for a connected graph $G$ of order $n$. Lov\''sz gave a path-cycle decomposition for a graph with at most $\lfloor\frac\rfloor$ paths and cycles, and gave an upper bound $\frac+g-1$ for $p(G)$. Dean and Kouider proved that $p(G)\leq\frac+\lfloor\fracg\rfloor$ for a general graph $G$, where $u$ is the number of odd vertex and $g$ is the number of nonisolated even vertex. Yan proved the same result independently. In this paper, we give a short proof for the same result by decomposing five cycles with a common vertex into six paths. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|