Bipartite graphs and digraphs with maximum connectivity
type: Item
instance of: scholarly article
title: Bipartite graphs and digraphs with maximum connectivity
zbMATH Open document ID: 0857.05063
DOI: 10.1016/0166-218X(95)00097-B
author: J. Fàbrega
author: Miquel Angel Fiol
published in: Discrete Applied Mathematics
publication date: 1997-03-06T00:00:00Z
review text: For a given bipartite digraph with diameter \(D\), let \(\ell\), \(1\leq \ell\leq D\), be the greatest integer such that for any two vertices \(x\) and \(y\) at distance \(d(x, y)\leq \ell\), the shortest \(x\)-\(y\) path is unique. The authors show that if the minimum degree \(\delta>1\) then the vertex connectivity \(\kappa=\delta\) whenever \(D\leq 2\ell\) and the edge connectivity \(\lambda=\delta\) whenever \(D\leq2\ell+1\). Analogous results are proved for bipartite graphs and for so-called superconnectivities.
reviewed by: Ján Plesník
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 933101
zbMATH Keywords: digraph
zbMATH Keywords: diameter
zbMATH Keywords: vertex connectivity
zbMATH Keywords: edge connectivity
zbMATH Keywords: superconnectivities
MaRDI profile type: Publication
cites work: On the linegraph of a directed-graph
cites work: Large fault-tolerant interconnection networks
cites work: Q4770409
cites work: Q3794213
cites work: Q3818315
cites work: On a problem of a. kotzig concerning factorizations of 4‐regular graphs
cites work: Maximally connected digraphs
cites work: Q3490015
cites work: The connectivity of large digraphs and graphs
cites work: Dense bipartite digraphs
cites work: Line Digraph Iterations and the (d, k) Digraph Problem
cites work: Q5629652
cites work: Results on the edge-connectivity of graphs
cites work: Q4079637
cites work: Q3356329
cites work: Sufficient conditions for maximally connected dense graphs
description: scientific article; zbMATH DE number 933101