{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:31:25Z","timestamp":1771036285757,"version":"3.50.1"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>Given a graph $G = (V,E)$, a vertex subset $S \\subseteq V$ is called $t$-stable (or $t$-dependent) if the subgraph $G[S]$ induced on $S$ has maximum degree at most $t$.  The $t$-stability number $\\alpha_t(G)$ of $G$ is the maximum order of a $t$-stable set in $G$.  The theme of this paper is the typical values that this parameter takes on a random graph on $n$ vertices and edge probability equal to $p$.  For any fixed $0  &lt;  p  &lt;  1$ and fixed non-negative integer $t$, we show that, with probability tending to $1$ as $n\\to\\infty$, the $t$-stability number takes on at most two values which we identify as functions of $t$, $p$ and $n$.  The main tool we use is an asymptotic expression for the expected number of $t$-stable sets of order $k$. We derive this expression by performing a precise count of the number of graphs on $k$ vertices that have maximum degree at most $t$.<\/jats:p>","DOI":"10.37236\/331","type":"journal-article","created":{"date-parts":[[2020,1,10]],"date-time":"2020-01-10T23:14:15Z","timestamp":1578698055000},"source":"Crossref","is-referenced-by-count":13,"title":["The $t$-Stability Number of a Random Graph"],"prefix":"10.37236","volume":"17","author":[{"given":"Nikolaos","family":"Fountoulakis","sequence":"first","affiliation":[]},{"given":"Ross J.","family":"Kang","sequence":"additional","affiliation":[]},{"given":"Colin","family":"McDiarmid","sequence":"additional","affiliation":[]}],"member":"23455","published-online":{"date-parts":[[2010,4,19]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v17i1r59\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v17i1r59\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,17]],"date-time":"2020-01-17T18:56:49Z","timestamp":1579287409000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v17i1r59"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,4,19]]},"references-count":0,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2010,1,5]]}},"URL":"https:\/\/doi.org\/10.37236\/331","relation":{},"ISSN":["1077-8926"],"issn-type":[{"value":"1077-8926","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,4,19]]},"article-number":"R59"}}