An Algorithm for the Decomposition of Complete Graph into Minimum Number of Edge-disjoint Trees
<|reference_start|>An Algorithm for the Decomposition of Complete Graph into Minimum Number of Edge-disjoint Trees: In this work, we study methodical decomposition of an undirected, unweighted complete graph ($K_n$ of order $n$, size $m$) into minimum number of edge-disjoint trees. We find that $x$, a positive integer, is minimum and $x=\lceil\frac{n}{2}\rceil$ as the edge set of $K_n$ is decomposed into edge-disjoint trees of size sequence $M = \{m_1,m_2,...,m_x\}$ where $m_i\le(n-1)$ and $\Sigma_{i=1}^{x} m_i$ = $\frac{n(n-1)}{2}$. For decomposing the edge set of $K_n$ into minimum number of edge-disjoint trees, our proposed algorithm takes total $O(m)$ time.<|reference_end|>
@article{sinha2024an,
    title={An Algorithm for the Decomposition of Complete Graph into Minimum Number
  of Edge-disjoint Trees},
    author={Antika Sinha, Sanjoy Kumar Saha and Partha Basuchowdhuri},
    journal={arXiv preprint arXiv:2405.18506},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.18506},
    primaryClass={cs.DM}
}