I tiakina i:
| Kaituhi matua: | |
|---|---|
| Hōputu: | Preprint |
| I whakaputaina: |
2020
|
| Ngā marau: | |
| Urunga tuihono: | https://arxiv.org/abs/2004.12986 |
| Ngā Tūtohu: |
Tāpirihia he Tūtohu
Kāore He Tūtohu, Me noho koe te mea tuatahi ki te tūtohu i tēnei pūkete!
|
Rārangi ihirangi:
- We consider the following question. We have a dense regular graph $G$ with degree $αn$, where $α>0$ is a constant. We add $m=o(n^2)$ random edges. The edges of the augmented graph $G(m)$ are given independent edge weights $X(e)$, $e\in E(G(m))$. We estimate the minimum weight of some specified combinatorial structures. We show that in certain cases, we can obtain the same estimate as is known for the complete graph, but scaled by a factor $α^{-1}$. We consider spanning trees, shortest paths, perfect matchings in (pseudo-random) bipartite graphs.