*Arthur Benjamin, Gary Chartrand, and Ping Zhang*

- Published in print:
- 2017
- Published Online:
- May 2018
- ISBN:
- 9780691175638
- eISBN:
- 9781400852000
- Item type:
- chapter

- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691175638.003.0003
- Subject:
- Mathematics, Applied Mathematics

This chapter considers distance in graphs, first by providing an overview of some fundamental concepts in graph theory. In particular, it discusses connected graphs, cut-vertex and bridge, and ...
More

This chapter considers distance in graphs, first by providing an overview of some fundamental concepts in graph theory. In particular, it discusses connected graphs, cut-vertex and bridge, and bipartite graphs. It then addresses questions of the distance between locations in a graph and those locations that are far from or close to a given location. It also looks at dominating sets in graphs, focusing on the Five Queens Problem/Puzzle and the Lights Out Puzzle, before concluding with an analysis of the rather humorous concept of Erdős numbers, conceptualized by Hungarian mathematician Paul Erdős. According to this concept, for each mathematician A, the Erdős number of A is the distance from A to Erdős in the collaboration graph. Consequently, Erdős is the only mathematician with the Erdős number 0, whereas any mathematician who has coauthored a paper with Erdős has Erdős number 1.Less

This chapter considers distance in graphs, first by providing an overview of some fundamental concepts in graph theory. In particular, it discusses connected graphs, cut-vertex and bridge, and bipartite graphs. It then addresses questions of the distance between locations in a graph and those locations that are far from or close to a given location. It also looks at dominating sets in graphs, focusing on the Five Queens Problem/Puzzle and the Lights Out Puzzle, before concluding with an analysis of the rather humorous concept of Erdős numbers, conceptualized by Hungarian mathematician Paul Erdős. According to this concept, for each mathematician *A*, the Erdős number of *A* is the distance from *A* to Erdős in the collaboration graph. Consequently, Erdős is the only mathematician with the Erdős number 0, whereas any mathematician who has coauthored a paper with Erdős has Erdős number 1.