go-v.orgdoi

The $t$-Stability Number of a Random Graph

Nikolaos Fountoulakis, Ross J. Kang, Colin McDiarmid · The Electronic Journal of Combinatorics · 2010

  • DOI 10.37236/331
  • Publisher Electronic Journal of Combinatorics
  • Type article
  • Issued 2010

Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.

The Electronic Journal of Combinatorics · Electronic Journal of Combinatorics · article · 2010

Abstract

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 < p < 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$.

Open the resolved locator · 10.37236/331

Metadata licence: OpenAlex metadata (CC0)