The connectivity of large digraphs and graphs
Let \(G\) denote a directed graph on \(n<\infty\) vertices and \(m\) arcs, with maximum in- or out-valence \(\Delta\), minimum in- or out-valence \(\delta>1\), diameter \(D\), connectivity \(\kappa\), and arc-connectivity \(\lambda\). It is well known that \(n \leq n(\Delta,D):=(\Delta^{D+1}- 1)/(\Delta-1)\), called the Moore bound. For integer \(p (0 \leq p \leq \delta-2)\), define \(\ell(p)\) for \(1 \leq \ell(p) \leq D\) to be the largest integer such that for any vertices \(x,y\) if distance \(d(x,y) \leq \ell(p)\), then there is a unique shortest directed \(xy\)-path and, moreover, if \(d(x,y)<\ell(p)\), then there are \(\leq p\) shortest \(xy\)-paths of length \(d(x,y)+1\). It is shown that if \(\kappa<\delta-p\), then \[ n \leq \kappa \biggl[ n \bigl( \Delta,D-\ell(p) \bigr)+n \bigl( \Delta,\ell(p)-1 \bigr)- 2 \biggr] + \Delta^{\ell(p)}+1; \] if \(\lambda<\delta-p\), then \[ m \leq \lambda \biggl[ n \bigl( \Delta,D-\ell(p) \bigr) +n \bigl( \Delta,\ell(p) \bigr)-2 \biggr]+\Delta^{\ell(p)}+1. \] Special cases are considered for iterated arc-graphs and for undirected graphs.
- Super-connected arc-transitive digraphs
- On the connectivity of \(p\)-diamond-free graphs
- Sufficient conditions for maximally connected dense graphs
- An inequality relating the order, maximum degree, diameter and connectivity of a strongly connected digraph
- Superconnectivity of bipartite digraphs and graphs
- The superconnectivity of large digraphs and graphs
- On the \(l\)-connectivity of a digraph
- On the order and size of s-geodetic digraphs with given connectivity
- Connectivity of large bipartite digraphs and graphs
- Bipartite graphs and digraphs with maximum connectivity
- Size of graphs and digraphs with given diameter and connectivity constraints
- Maximally edge-connected graphs and zeroth-order general Randić index for \(0<\alpha <1\)
- On local connectivity of graphs
- High connectivity keeping sets in graphs and digraphs
- scientific article; zbMATH DE number 4019097 (Why is no real title available?)
- On computing the connectivities of graphs and digraphs
- scientific article; zbMATH DE number 4162914 (Why is no real title available?)
- scientific article; zbMATH DE number 3910097 (Why is no real title available?)
- Maximally connected digraphs
- Graphs, friends and acquaintances
- On local connectivity of graphs with given clique number
- scientific article; zbMATH DE number 2188339 (Why is no real title available?)
- The connectivity and minimum degree of circuit graphs of matroids
- Maximally edge-connected graphs and zeroth-order general Randić index for -1
- Lower bounds on the vertex-connectivity of digraphs and graphs
- Maximally edge-connected and vertex-connected graphs and digraphs: A survey
This page was built for publication: The connectivity of large digraphs and graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4693342)
