Upper bounds on distance measures in K3,3-free graphs

Abstract

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 ₄-free graphs. Dankelmann and Entringer gave an analogous bound for the average distance in C₄-free graphs. In this paper, we give upper bounds on the diameter, radius and average distance of K_3,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.