Upper bounds on distance measures in K3,3-free graphs - Dankelmann, Peter; Dlamini, Gcina; Swart, Henda C. (Utilitas Mathematica, 2005)
Let G be a connected graph of order n and minimum degree S. Erdös, Fach, Pollack and Tuza showed that the well known upper bounds [3n/δ+1] - 1 and 2/3 n-3/δ+1 + 5 on the diameter and radius, respectively, can be improved to bounds of the order of magnitude O(n/δ2) for C 4-free graphs. Dankelmann and Entringer gave an analogous bound for the average distance in C4-free graphs. In this paper, we give upper bounds on the diameter, radius and average distance of K3,3-free graphs. The bounds are of the order of magnitude O(n/δ3/2) We construct graphs that show that the order of magnitude is best possible.