An Algorithm for the Decomposition of Complete Graph into Minimum Number of Edge-disjoint Trees
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929363412320256 |
|---|---|
| author | Sinha, Antika Saha, Sanjoy Kumar Basuchowdhuri, Partha |
| author_facet | Sinha, Antika Saha, Sanjoy Kumar Basuchowdhuri, Partha |
| contents | 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 $Σ_{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_18506 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An Algorithm for the Decomposition of Complete Graph into Minimum Number of Edge-disjoint Trees Sinha, Antika Saha, Sanjoy Kumar Basuchowdhuri, Partha Discrete Mathematics 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 $Σ_{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. |
| title | An Algorithm for the Decomposition of Complete Graph into Minimum Number of Edge-disjoint Trees |
| topic | Discrete Mathematics |
| url | https://arxiv.org/abs/2405.18506 |