The t-stability number of a random graph

Details The t-stability number of a random graph The t-stability number of a random graph

2008-08-31

arxiv.org/abs/0809.0141v2

Electron. J. Combin. 17 (2010), #R59

Mathematics

Combinatorics

25 pages; v2 has 30 pages and is identical to the journal version apart from formatting and a minor amendment to Lemma 8 (and

Scientific paper

Given a graph G = (V,E), a vertex subset S 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 of G is the maximum order of a t-stable set in G. We investigate 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 grows, 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 k. Using the above results, we also obtain asymptotic bounds on the t-improper chromatic number of a random graph (this is the generalisation of the chromatic number, where we partition of the vertex set of the graph into t-stable sets).

Affiliated with

Also associated with

No associations

Rating

The t-stability number of a random graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The t-stability number of a random graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The t-stability number of a random graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-578880