## 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 _{4}-free graphs. Dankelmann and Entringer gave an analogous bound for the average distance in C_{4}-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.

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

Pages (from-to) | 205-221 |

Number of pages | 17 |

Journal | Utilitas Mathematica |

Volume | 67 |

Publication status | Published - May 2005 |

Externally published | Yes |

## ASJC Scopus subject areas

- Statistics and Probability
- Statistics, Probability and Uncertainty
- Applied Mathematics

## Fingerprint

Dive into the research topics of 'Upper bounds on distance measures in K_{3,3}-free graphs'. Together they form a unique fingerprint.