PreprintCC BY 4.0arXiv
The toughness of random graphs
Abstract
For a connected and non-complete graph G of order n, its toughness is defined as τ(G)=min{|S|/c(G−S):S⊆ V(G), c(G−S)>1}, where c(G−S) denotes the number of components of G−S. Let α(G) denote the independence number of G. An elementary bound on toughness is τ(G)≤(n−α(G))/α(G). Fix p∈(0,1), and let G(n,p) be the binomial random graph on vertex set [n]. Set a=α(G(n,p)). In this paper, we mainly prove that τ(G(n,p))∈{(n−a)/a,(n−a−1)/a} with high probability.
Related
BibTeX
@misc{li2026toughness,
title = {{The toughness of random graphs}},
author = {Guang Li and Wenqian Zhang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.31056},
eprint = {2608.31056},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.31056},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The toughness of random graphs
AU - Guang Li
AU - Wenqian Zhang
PY - 2026
DA - 2026/09/05
PB - arXiv
DO - 10.48550/arxiv.2608.31056
UR - https://arxiv.org/abs/2608.31056
AB - For a connected and non-complete graph G of order n, its toughness is defined as τ(G)=min{|S|/c(G−S):S⊆ V(G), c(G−S)>1}, where c(G−S) denotes the number of components of G−S. Let α(G) denote the independence number of G. An elementary bound on toughness is τ(G)≤(n−α(G))/α(G). Fix p∈(0,1), and let G(n,p) be the binomial random graph on vertex set [n]. Set a=α(G(n,p)). In this paper, we mainly prove that τ(G(n,p))∈{(n−a)/a,(n−a−1)/a} with high probability.
ER -