{"id":"arxiv/2608.31056","url":"https://arxiv.org/abs/2608.31056","tags":["math.CO"],"score":0,"title":"The toughness of random graphs","domain":"math.CO","source":"arxiv","authors":["Guang Li","Wenqian Zhang"],"reviews":0,"subject":"math.CO","summary":"For a connected and non-complete graph $G$ of order $n$, its toughness is defined as \\[ τ(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 $α(G)$ denote the independence number of $G$. An elementary bound on toughness is $$τ(G)\\leq\\frac{n-α(G)}{α(G)}.$$ Fix $p\\in(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))\\in\\left\\{\\frac{n-a}{a},\\frac{n-a-1}{a}\\right\\} \\] with high probability.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-31","reactions":{}}