Regular induced subgraphs of a random graph

Details Regular induced subgraphs of a random graph Regular induced subgraphs of a random graph

2008-08-14

arxiv.org/abs/0808.2023v1

Mathematics

Combinatorics

Scientific paper

An old problem of Erd\H{o}s, Fajtlowicz and Staton asks for the order of a largest induced regular subgraph that can be found in every graph on n vertices. Motivated by this problem, we consider the order of such a subgraph in a typical graph on n vertices, i.e., in a binomial random graph G(n,1/2). We prove that with high probability a largest induced regular subgraph of G(n,1/2) has about n^{2/3} vertices.

Affiliated with

Also associated with

No associations

Rating

Regular induced subgraphs 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 Regular induced subgraphs of a random graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Regular induced subgraphs of a random graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-584831