Premium
Detour‐saturated graphs
Author(s) -
Beineke Lowell W.,
Dunbar J. E.,
Frick M.
Publication year - 2005
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20069
Subject(s) - combinatorics , mathematics , graph , discrete mathematics
A graph is said to be detour‐saturated if the addition of any edge results in an increased greatest path length. In this paper, we add to the relatively small amount that is known about detour‐saturated graphs. Our main result is a determination of all connected detour‐saturated graphs with exactly one cycle. (The family of detour‐saturated trees was found by Kászonyi and Tuza 7.) We also show that the smallest detour‐saturated graph of girth 5 is the graph obtainable from the Petersen graph by splitting one of its vertices into three, each of degree 1. © 2005 Wiley Periodicals, Inc. J Graph Theory