Metraipolis › archive › dc_54707bdbabb8

The toughness of random graphs — arXiv:2608.31056

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.31056
License (as archived)
CC0-1.0
Archived
2026-10-17T09:31:16.277Z
SHA-256 of the archived text
93168343358be4c16f4d4e9fc3fa7b68ffbbe637e4a9e2869b42c04ab7f50bc1
Stable URL of this page
https://metraipolis.com/documento/dc_54707bdbabb8

How to cite

The toughness of random graphs — arXiv:2608.31056 — arXiv (en), https://arxiv.org/abs/2608.31056 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_54707bdbabb8 (Metraipolis archive dc_54707bdbabb8, sha256 93168343358be4c16f4d4e9fc3fa7b68ffbbe637e4a9e2869b42c04ab7f50bc1)
BibTeX
@misc{dc54707bdbabb8,
  title = {The toughness of random graphs — arXiv:2608.31056},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.31056},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_54707bdbabb8; sha256 93168343358be4c16f4d4e9fc3fa7b68ffbbe637e4a9e2869b42c04ab7f50bc1},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.31056. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

For a connected and non-complete graph $G$ of order $n$, its toughness is defined as \[ \tau(G)=\min\bigl\{|S|/c(G-S):S\subseteq V(G),\ c(G-S)>1\bigr\}, \] where $c(G-S)$ denotes the number of components of $G-S$. Let $\alpha(G)$ denote the independence number of $G$. An elementary bound on toughness is $$\tau(G)\leq\frac{n-\alpha(G)}{\alpha(G)}.$$ Fix $p\in(0,1)$, and let $G(n,p)$ be the binomial random graph on vertex set $[n]$. Set $a=\alpha(G(n,p))$. In this paper, we mainly prove that \[ \tau(G(n,p))\in\left\{\frac{n-a}{a},\frac{n-a-1}{a}\right\} \] with high probability.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-01 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2608.31056 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T09:02:28.870Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).