TY - JOUR

T1 - Regular graphs of large girth and arbitrary degree

AU - Dahan, Xavier

N1 - Funding Information:
* Supported by the GCOE Project “Math-for-Industry” of Kyushu University
Publisher Copyright:
© 2014, János Bolyai Mathematical Society and Springer-Verlag Berlin Heidelberg.

PY - 2014/8/1

Y1 - 2014/8/1

N2 - For every integer d≥10, we construct infinite families {Gn}n∈ℕ of d+1-regular graphs which have a large girth ≥logd|Gn|, and for d large enough ≥1.33 · logd|Gn|. These are Cayley graphs on PGL2(Fq) 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 a 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 {In}n∈ℕ of d + 1-regular graphs, realized as Cayley graphs on SL2(Fq), and which are displaying a girth ≥0.48·logd|In|. And when d is equal to a power of 2, this improves a construction by Morgenstern in 1994 where certain families {Mn}n∈N of 2k +1-regular graphs were shown to have girth ≥2/3·log2k|Mn|.

AB - For every integer d≥10, we construct infinite families {Gn}n∈ℕ of d+1-regular graphs which have a large girth ≥logd|Gn|, and for d large enough ≥1.33 · logd|Gn|. These are Cayley graphs on PGL2(Fq) 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 a 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 {In}n∈ℕ of d + 1-regular graphs, realized as Cayley graphs on SL2(Fq), and which are displaying a girth ≥0.48·logd|In|. And when d is equal to a power of 2, this improves a construction by Morgenstern in 1994 where certain families {Mn}n∈N of 2k +1-regular graphs were shown to have girth ≥2/3·log2k|Mn|.

KW - 05C25

KW - 05C38

UR - http://www.scopus.com/inward/record.url?scp=84908143828&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84908143828&partnerID=8YFLogxK

U2 - 10.1007/s00493-014-2897-6

DO - 10.1007/s00493-014-2897-6

M3 - Article

AN - SCOPUS:84908143828

SN - 0209-9683

VL - 34

SP - 407

EP - 426

JO - Combinatorica

JF - Combinatorica

IS - 4

ER -