The \(t\)-stability number of a random graph
The electronic journal of combinatorics, Tome 17 (2010)
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$.
@article{10_37236_331,
author = {Nikolaos Fountoulakis and Ross J. Kang and Colin McDiarmid},
title = {The \(t\)-stability number of a random graph},
journal = {The electronic journal of combinatorics},
year = {2010},
volume = {17},
doi = {10.37236/331},
zbl = {1222.05236},
url = {http://geodesic.mathdoc.fr/articles/10.37236/331/}
}
Nikolaos Fountoulakis; Ross J. Kang; Colin McDiarmid. The \(t\)-stability number of a random graph. The electronic journal of combinatorics, Tome 17 (2010). doi: 10.37236/331
Cité par Sources :