Nevil Anto ; Manu Basavaraju - Gallai's Path Decomposition for 2-degenerate Graphs

dmtcs:10313 - Discrete Mathematics & Theoretical Computer Science, May 30, 2023, vol. 25:1 - https://doi.org/10.46298/dmtcs.10313
Gallai's Path Decomposition for 2-degenerate GraphsArticle

Authors: Nevil Anto ; Manu Basavaraju

    Gallai's path decomposition conjecture states that if $G$ is a connected graph on $n$ vertices, then the edges of $G$ can be decomposed into at most $\lceil \frac{n }{2} \rceil$ paths. A graph is said to be an odd semi-clique if it can be obtained from a clique on $2k+1$ vertices by deleting at most $k-1$ edges. Bonamy and Perrett asked if the edges of every connected graph $G$ on $n$ vertices can be decomposed into at most $\lfloor \frac{n}{2} \rfloor$ paths unless $G$ is an odd semi-clique. A graph $G$ is said to be 2-degenerate if every subgraph of $G$ has a vertex of degree at most $2$. In this paper, we prove that the edges of any connected 2-degenerate graph $G$ on $n$ vertices can be decomposed into at most $\lfloor \frac{n }{2} \rfloor$ paths unless $G$ is a triangle.


    Volume: vol. 25:1
    Section: Graph Theory
    Published on: May 30, 2023
    Accepted on: May 4, 2023
    Submitted on: November 16, 2022
    Keywords: Mathematics - Combinatorics,Computer Science - Discrete Mathematics,05C38, 05C70,G.2.2

    Consultation statistics

    This page has been seen 409 times.
    This article's PDF has been downloaded 325 times.