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(Delta,D) be the largest order of a claw-free graph of maximum degree Delta and diameter D. We show that cf Delta (,D) <= 1 + 2 Sigma(D)(i=1) (Delta/2)(i)-c(Delta)(j)Sigma i=0(i=0)(D-2)(Delta/2)(i), where c(Delta)(j)=2(Delta/2)(2)/(Delta/2)(2)+Delta/2+2, for any D and any even Delta >= 4. So for claw-free graphs, the well-known Moore bound can be strengthened considerably. We further show that cf(Delta,2) >= 5/6(Delta+2)(2) for Delta >= 6 with Delta equivalent to 2 (mod 4). We also give an upper bound on the order of K-1,K-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 Delta, rank k, and diameter D is at most 1 + Delta Sigma(D)(i=1)(Delta - 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 Sigma(D)(i=1)(k - 1)(i) - c(k) Sigma i=(D-2)(i=0)(k - 1)(i), where c(k) = 2k(2) - 2k+1/k(2)-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. (c) 2013 Wiley Periodicals, Inc. J. Graph Theory 75: 105-123, 2014