The degree-diameter problem for claw-free graphs and hypergraphs

We study the degree-diameter problem for claw-free graphs and 2-regular hypergraphs. Let cf Δ,D be the largest order of a claw-free graph of maximum degree Δ and diameter D. We show that cf Δ,D≤1+2Σi= 1D(Δ2)i-cΔ′Σi=0D-2(Δ2)i, where cΔ′=2(Δ/2)2(Δ/2)2+Δ/2+2, for any D and any even Δ≥4. So for claw-free graphs, the well-known Moore bound can be strengthened considerably. We further show that cf Δ,2≥516(Δ+2)2 for Δ≥6 with Δ≡2 (mod 4). We also give an upper bound on the order of K1,p-free graphs of given maximum degree and diameter for p≥3. We prove similar results for the hypergraph version of the degree-diameter problem. The hypergraph Moore bound states that the order of a hypergraph of maximum degree Δ, rank k, and diameter D is at most 1+ΔΣi= 1D(Δ-1)i-1(k-1)i. For 2-regular hypergraph of rank k≥3 and any diameter D, we improve this bound to 1+2Σi=1D(k-1)i-ckΣi=0D-2(k-1)i, where ck=2k2-2k+1k2-k+2. Our construction of claw-free graphs of diameter 2 yields a similar result for hypergraphs of diameter 2, degree 2, and any even rank k≥4.