Extremal Regular Graphs with Prescribed Odd Girth

✍ Scribed by G.H. Zhang

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 496 KB
• Volume: 60
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1994.1015

✦ Synopsis

The odd girth of a graph (G) gives the length of a shortest odd cycle in (G). Let (f(k, g)) denote the smallest (n) such that there exists a (k)-regular graph of order (n) and odd girth (g). It is known that (f(k, g) \geqslant k g / 2) and that (f(k, g)=k g / 2) if (k) is even. The exact values of (f(k, g)) are also known if (k=3) or (g=5). Let (\lceil x\rceil), denote the smallest even integer no less than (x, \delta(g)=(-1)^{(k-1) 2}), and (s(k)=) (\min {p+q \mid k=p q), where (p) and (q) are both positive integers (}). It is proved that if (k \geqslant 5) and (g \geqslant 7) are both odd, then

[
f(k, g)= \begin{cases}\Gamma(k+1) g / 2\rceil & \text { if } k \text { is a prime or } s(k)+\delta(g)>g-2 \ (k g+s(k)+\delta(g)) / 2 & \text { otherwise }\end{cases}
]

with the exception that (/(5,7)=20). ' 1994 Academic Press. Inc