Premium
Superconnected digraphs and graphs with small conditional diameters
Author(s) -
Balbuena C.,
Fàbrega J.,
Marcote X.,
Pelayo I.
Publication year - 2002
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.10020
Subject(s) - combinatorics , digraph , corollary , mathematics , degree (music) , undirected graph , vertex (graph theory) , girth (graph theory) , discrete mathematics , graph , physics , acoustics
Abstract The conditional diameter D ν of a digraph G measures how far apart a pair of vertex sets V 1 and V 2 can be in such a way that the minimum out‐degree and the minimum in‐degree of the subdigraphs induced by V 1 and V 2 , respectively, are at least ν. Thus, D 0 is the standard diameter and D 0 ≥ D 1 ≥ ··· ≥ D δ , where δ is the minimum degree. We prove that if D ν ≤ 2l − 3, where l is a parameter related to the shortest paths, then G is maximally connected, is superconnected, or has a good superconnectivity, depending only on whether ν is equal to ⌈δ/2⌉, ⌈(δ − 1)/2⌉, or ⌈(δ − 1)/3⌉, respectively. In the edge case, it is enough that D ν ≤ 2l − 2. The results for graphs are obtained as a corollary of those for digraphs, because, in the undirected case, l = ⌊( g − 1)/2⌋, g being the girth. © 2002 Wiley Periodicals, Inc.