The Degree‐Diameter Problem for Claw‐Free Graphs and Hypergraphs |
| |
| Authors: | Peter Dankelmann Tomá? Vetrík |
| |
| Affiliation: | 1. DEPARTMENT OF MATHEMATICS, UNIVERSITY OF JOHANNESBURG, JOHANNESBURG, SOUTH AFRICA;2. DEPARTMENT OF MATHEMATICS AND APPLIED MATHEMATICS, UNIVERSITY OF PRETORIA, PRETORIA, SOUTH AFRICA |
| |
| Abstract: | We study the degree‐diameter problem for claw‐free graphs and 2‐regular hypergraphs. Let  be the largest order of a claw‐free graph of maximum degree Δ and diameter D. We show that  , where  , for any D and any even  . So for claw‐free graphs, the well‐known Moore bound can be strengthened considerably. We further show that  for  with  (mod 4). We also give an upper bound on the order of  ‐free graphs of given maximum degree and diameter for  . 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  . For 2‐regular hypergraph of rank  and any diameter D, we improve this bound to  , where  . Our construction of claw‐free graphs of diameter 2 yields a similar result for hypergraphs of diameter 2, degree 2, and any even rank  . |
| |
| Keywords: | claw‐free graph hypergraph degree diameter Moore geometry |
|
|
