Conditional diameter saturated graphs

The conditional diameter D ( G ) of a connected graph G is a measure of the maximum distance between two subsets of vertices satisfying a given property of interest. For any given integer k ≥ 1, a connected graph G is said to be conditional diameter k ‐saturated if D ( G ) ≥ k and there does not exist any other connected graph G′ with order ∣ V ( G′ )∣ = ∣ V ( G )∣, size ∣ E ( G′ )∣ > ∣ E ( G )∣, and conditional diameter D ( G′ ) ≥ k . In this article, we obtain such conditional diameter saturated graphs for a number of properties , generalizing the results obtained in (Ore, J Combin Theory 5(1968), 75–81) for the (standard) diameter D ( G ). © 2008 Wiley Periodicals, Inc. NETWORKS, 2008