Abstract | ||
---|---|---|
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). Let δ, κ and λ be respectively the minimum degree, (vertex-) connectivity and arc-connectivity of G . The digraph G is said to be super-κ if all its minimum disconnecting sets are trivial. Analogously, G is called super-λ if all its minimum arc-disconnecting sets are trivial. In this paper it is proved that G is super-κ if n>δ{n(Δ,D−l)+n(Δ,l−1)−2}+Δ D−l+1 +1; G is super-λ if n>δ{n(Δ,D−l−1)+n(Δ,l−1)}+Δ D−1 , where l stands for a parameter related with the number of short paths. Similar results are given for graphs (in this case it turns out that l =⌊( g −1)/2⌋ where g stands for the girth). |
Year | DOI | Venue |
---|---|---|
1994 | 10.1016/0012-365X(92)00051-R | Discrete Mathematics |
Keywords | Field | DocType |
large digraph | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Degree (graph theory),Moore bound,Digraph,Mathematics | Journal |
Volume | Issue | ISSN |
124 | 1 | Discrete Mathematics |
Citations | PageRank | References |
8 | 0.94 | 9 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
M. A. Fiol | 1 | 816 | 87.28 |