Premium
Connectedness of digraphs and graphs under constraints on the conditional diameter
Author(s) -
Marcote X.,
Balbuena C.,
Fàbrega J.
Publication year - 2005
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.20051
Subject(s) - digraph , combinatorics , social connectedness , corollary , mathematics , vertex (graph theory) , degree (music) , graph , discrete mathematics , strongly connected component , physics , psychology , acoustics , psychotherapist
Given a digraph G with minimum degree δ and an integer 0≤ ν ≤ δ , consider every pair of vertex subsets V 1 and V 2 such that both the minimum out‐degree of the induced subdigraph G [ V 1 ] and the minimum in‐degree of G [ V 2 ] are at least ν . The conditional diameter D ν of G is defined as the maximum of the distances d ( V 1 , V 2 ) between any two such vertex subsets. Clearly, D 0 is the standard diameter and D 0 ≥ D 1 ≥ ··· ≥ D δ holds. In this article, we guarantee appropriate lower bounds for the connectivities and superconnectivities of a digraph G when D ν ≤ h ( ℓ π ), h ( ℓ π ) being a function of the parameter ℓ π —which is related to the shortest paths in G . As a corollary of these results, we give some constraints of the kind D ν ≤ h ( ℓ π ), which assure that the digraph is maximally connected, maximally edge‐connected, superconnected, or edge‐superconnected, extending other previous results of the same kind. Similar statements can be obtained for a graph as a direct consequence of those for its associated symmetric digraph. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(2), 80–87 2005