Premium
Conditional diameter saturated graphs
Author(s) -
Balbuena C.,
GarcíaVázquez P.,
Marcote X.,
Valenzuela J.C.
Publication year - 2008
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20230
Subject(s) - combinatorics , mathematics , graph , discrete mathematics , integer (computer science) , connectivity , computer science , programming language
Abstract 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