Handbook of Graph Theory, 2nd Edition

Chapter 9

Graphical Measurement

Section 9.1 Distance in Graphs

Gary Chartrand

Western Michigan University

Ping Zhang

Western Michigan University

Introduction

How far two objects (or sets of objects) are apart in a discrete structure is of interest, both theoretically and for its applications. Since discrete structures are naturally modeled by graphs, this leads us to studying distance in graphs. A book entirely devoted to this subject has been written (see [BuHa90]).

9.1.1 Standard Distance in Graphs

Although there is not a unique way to define the distance between two vertices in a graph, there is one definition of distance that has been used most often and is commonly accepted as the standard definition of distance.

Distance and Eccentricity ...