Chapter 9

Graphical Measurement

Section 9.1 Distance in Graphs

Gary Chartrand

Western Michigan University

Ping Zhang

Western Michigan University


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 ...

Get Handbook of Graph Theory, 2nd Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.