## Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 105-123 |

Number of pages | 19 |

Journal | Journal of Graph Theory |

Volume | 75 |

Issue number | 2 |

DOIs | |

Publication status | Published - Feb 2014 |

## Keywords

- Moore geometry
- claw-free graph
- degree
- diameter
- hypergraph

## ASJC Scopus subject areas

- Geometry and Topology
- Discrete Mathematics and Combinatorics