Large (d,D,D',s)-bipartite digraphs

Large (d,D,D',s)-bipartite digraphs

0.00 Avg rating0 Votes
Article ID: iaor1997994
Country: Netherlands
Volume: 59
Issue: 2
Start Page Number: 103
End Page Number: 114
Publication Date: May 1995
Journal: Discrete Applied Mathematics
Authors: , ,
Keywords: networks
Abstract:

A (d,D,D',s)-digraph is a directed graph with diameter D and maximum out-degree d such that after the deletion of any s of its vertices the resulting digraph has diameter at most D'. The present concern is to find large, i.e. with order as large as possible, (d,D,D',s)-bipartite digraphs. To this end, it is proved that some members of a known family of large bipartite digraphs satisfy a Menger-type condition. Namely, between any pair of non-adjacent vertices they have s+1 internally disjoint paths of length at most D'. Then, a new family of (d,D,D',s)-bipartite digraphs with order very close to the upper bound is obtained.

Reviews

Required fields are marked *. Your email address will not be published.