On the power of BFS to determine a graph's diameter

Abstract

Abstract Recently, considerable effort has been spent on showing that Lexicographic Breadth First Search (LBFS) can be used to determine a tight bound on the diameter of graphs from various restricted classes. In this paper, we show that, in some cases, the full power of LBFS is not required and that other variations of Breadth First Search (BFS) suffice. The restricted graph classes that are amenable to this approach all have a small constant upper bound on the maximum‐sized cycle that may appear as an induced subgraph. We show that, on graphs that have no induced cycle of size greater than k , BFS finds an estimate of the diameter that is no worse than diam( G ) − ⌊ k /2⌋. © 2003 Wiley Periodicals, Inc.