The number of graphs of given diameter

Details The number of graphs of given diameter The number of graphs of given diameter

2012-04-20

arxiv.org/abs/1204.4580v1

Mathematics

Combinatorics

13 pages

Scientific paper

In this paper it is proved that there are constants 0< c_2< c_1 such that an asymptotic formula can be given for the the number of (labeled) n-vertex graphs of diameter d whenever n tends to infinity and 2 < d < n - c_1 (log n). A typical graph of diameter d consists of a combination of an induced path of length d and a highly connected block of size n-d+3. In the case d > n- c_2(log n) another asymptotic formula is calculated and the typical graph has a completely different snakelike structure.

Affiliated with

Also associated with

No associations

Rating

The number of graphs of given diameter 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 number of graphs of given diameter, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The number of graphs of given diameter will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-5493