*Ping Zhang, Gary Chartrand, and Arthur Benjamin*

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

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

Graph theory goes back several centuries and revolves around the study of graphs—mathematical structures showing relations between objects. With applications in biology, computer science, ...
More

Graph theory goes back several centuries and revolves around the study of graphs—mathematical structures showing relations between objects. With applications in biology, computer science, transportation science, and other areas, graph theory encompasses some of the most beautiful formulas in mathematics—and some of its most famous problems. This book explores the questions and puzzles that have been studied, and often solved, through graph theory. It looks at graph theory's development and the vibrant individuals responsible for the field's growth. Introducing fundamental concepts, the book explores a diverse plethora of classic problems such as the Lights Out Puzzle, and each chapter contains math exercises for readers to savor. An eye-opening journey into the world of graphs, the book offers exciting problem-solving possibilities for mathematics and beyond.Less

Graph theory goes back several centuries and revolves around the study of graphs—mathematical structures showing relations between objects. With applications in biology, computer science, transportation science, and other areas, graph theory encompasses some of the most beautiful formulas in mathematics—and some of its most famous problems. This book explores the questions and puzzles that have been studied, and often solved, through graph theory. It looks at graph theory's development and the vibrant individuals responsible for the field's growth. Introducing fundamental concepts, the book explores a diverse plethora of classic problems such as the Lights Out Puzzle, and each chapter contains math exercises for readers to savor. An eye-opening journey into the world of graphs, the book offers exciting problem-solving possibilities for mathematics and beyond.

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