Premium
The connectivity of large digraphs and graphs
Author(s) -
Fiol M. A.
Publication year - 1993
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190170105
Subject(s) - digraph , combinatorics , mathematics , girth (graph theory) , degree (music) , graph , order (exchange) , discrete mathematics , upper and lower bounds , physics , economics , mathematical analysis , acoustics , finance
This paper studies the relation between the connectivity and other parameters of a digraph (or graph), namely its order n , minimum degree δ, maximum degree Δ, diameter D , and a new parameter l pi; , 0 ≤ π ≤ δ − 2, related with the number of short paths (in the case of graphs l 0 = ⌊( g − 1)/2⌋ where g stands for the girth). For instance, let G = ( V,A ) be a digraph on n vertices with maximum degree Δ and diameter D , so that n ≤ n (Δ, D ) = 1 + Δ + Δ 2 + … + Δ D (Moore bound). As the main results it is shown that, if κ and λ denote respectively the connectivity and arc‐connectivity of G ,. Analogous results hold for graphs. © 1993 John Wiley & Sons, Inc.