Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2411.03133 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929577231646720 |
|---|---|
| author | Pizzimenti, Anthony E. Rakhimov, Umarkhon |
| author_facet | Pizzimenti, Anthony E. Rakhimov, Umarkhon |
| contents | The Harary reconstruction conjecture states that any graph with more than four edges can be uniquely reconstructed from its set of maximal edge-deleted subgraphs. In 1977, Müller verified the conjecture for graphs with $n$ vertices and $n \log_2(n)$ edges, improving on Lovás's bound of $\log(n^2-n)/4$. Here, we show that the reconstruction conjecture holds for graphs which have exactly one cycle and and three non-isomorphic subtrees. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_03133 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Reconstructing edge-deleted unicyclic graphs Pizzimenti, Anthony E. Rakhimov, Umarkhon Combinatorics Data Structures and Algorithms The Harary reconstruction conjecture states that any graph with more than four edges can be uniquely reconstructed from its set of maximal edge-deleted subgraphs. In 1977, Müller verified the conjecture for graphs with $n$ vertices and $n \log_2(n)$ edges, improving on Lovás's bound of $\log(n^2-n)/4$. Here, we show that the reconstruction conjecture holds for graphs which have exactly one cycle and and three non-isomorphic subtrees. |
| title | Reconstructing edge-deleted unicyclic graphs |
| topic | Combinatorics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2411.03133 |