| Abstract: | 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 |
