E-viri
Odprti dostop
-
Aigner-Horev, Elad; Hefetz, Dan; Krivelevich, Michael
arXiv.org, 12/2022Paper, Journal Article
Extremal properties of sparse graphs, randomly perturbed by the binomial random graph are considered. It is known that every \(n\)-vertex graph \(G\) contains a complete minor of order \(\Omega(n/\alpha(G))\). We prove that adding \(\xi n\) random edges, where \(\xi > 0\) is arbitrarily small yet fixed, to an \(n\)-vertex graph \(G\) satisfying \(\alpha(G) \leq \zeta(\xi)n\) asymptotically almost surely results in a graph containing a complete minor of order \(\tilde \Omega \left( n/\sqrt{\alpha(G)}\right)\); this result is tight up to the implicit logarithmic terms. For complete topological minors, we prove that there exists a constant \(C>0\) such that adding \(C n\) random edges to a graph \(G\) satisfying \(\delta(G) = \omega(1)\), asymptotically almost surely results in a graph containing a complete topological minor of order \(\tilde \Omega(\min\{\delta(G),\sqrt{n}\})\); this result is tight up to the implicit logarithmic terms. Finally, extending results of Bohman, Frieze, Krivelevich, and Martin for the dense case, we analyse the asymptotic behaviour of the vertex-connectivity and the diameter of randomly perturbed sparse graphs.
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Vnos na polico
Trajna povezava
- URL:
Faktor vpliva
Dostop do baze podatkov JCR je dovoljen samo uporabnikom iz Slovenije. Vaš trenutni IP-naslov ni na seznamu dovoljenih za dostop, zato je potrebna avtentikacija z ustreznim računom AAI.
Leto | Faktor vpliva | Izdaja | Kategorija | Razvrstitev | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Baze podatkov, v katerih je revija indeksirana
Ime baze podatkov | Področje | Leto |
---|
Povezave do osebnih bibliografij avtorjev | Povezave do podatkov o raziskovalcih v sistemu SICRIS |
---|
Vir: Osebne bibliografije
in: SICRIS
To gradivo vam je dostopno v celotnem besedilu. Če kljub temu želite naročiti gradivo, kliknite gumb Nadaljuj.