Arbitrary degree regular graphs of large girth

Details Arbitrary degree regular graphs of large girth Arbitrary degree regular graphs of large girth

2011-10-24

arxiv.org/abs/1110.5259v3

Mathematics

Combinatorics

15 pages

Scientific paper

For every integer d > 9, we construct infinite families {G_n}_n of d+1-regular graphs which have a large girth > log_d |G_n|, and for d large enough > 1,33 log_d |G_n|. These are Cayley graphs on PGL_2(q) for a special set of d+1 generators whose choice is related to the arithmetic of integral quaternions. These graphs are inspired by the Ramanujan graphs of Lubotzky-Philips-Sarnak and Margulis, with which they coincide when d is prime. When d is not equal to the power of an odd prime, this improves the previous construction of Imrich in 1984 where he obtained infinite families {I_n}_n of d+1-regular graphs, realized as Cayley graphs on SL_2(q), and which are displaying a girth > 0,48 log_d |I_n|. And when d is equal to a power of 2, this improves a construction by Morgenstern in 1994 where certain families {M_n}_n of 2^k+1-regular graphs were shown to have a girth > 2/3 log_d |M_n|.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-520863