On the distance connectivity of graphs and digraphs
type: Item
instance of: scholarly article
title: On the distance connectivity of graphs and digraphs
zbMATH Open document ID: 0796.05058
DOI: 10.1016/0012-365X(94)90157-0
author: J. Fàbrega
author: Miquel Angel Fiol
published in: Discrete Mathematics
publication date: 1994-09-15T00:00:00Z
review text: In a finite connected directed graph \(G=(V,E)\) of diameter \(D\), define the parameter \(l=l(G)\) to be the greatest integer \(\leq D\) such that for all \(x,y \in V\), with directed distance \(d(x,y) \leq l\), there exists a unique \(x \to y\) path of length \(d(x,y)\), while if \(d(x,y)<l\), then there is none of length \(d(x,y)+1\). For \(1 \leq t \leq D\), define \(\kappa (t)=\min \{| S |:S\) separates \(y\) from \(x\); \(x,y \in V\); \(d(x,y) \geq t\}\). Let \(\kappa\) and \(\lambda\) denote the usual vertex- and edge- connectivity of \(G\). It is shown that if \(G\) has minimum valence \(r>1\), then: (a) if \(\kappa<r\), then \(D \geq 2l\) and \(\kappa = \kappa (2l)\); (b) if \(\lambda<r\), then \(D \geq 2l+1\) and \(\lambda = \lambda (2l+1)\). Results for (undirected) graphs are obtained as corollaries. In the special case of bipartite directed graphs, the second condition in the definition of \(l\) being vacuous, slightly sharper inequalities may be obtained.
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 562660
zbMATH Keywords: distance connectivity
zbMATH Keywords: maximally connected
zbMATH Keywords: girth
zbMATH Keywords: directed graph
zbMATH Keywords: diameter
zbMATH Keywords: directed distance
zbMATH Keywords: edge-connectivity
zbMATH Keywords: valence
zbMATH Keywords: inequalities
reviewed by: Mark E. Watkins
MaRDI profile type: Publication
cites work: On the linegraph of a directed-graph
cites work: Large fault-tolerant interconnection networks
cites work: Q3818315
cites work: Maximally connected digraphs
cites work: Bipartite graphs and digraphs with maximum connectivity
cites work: Q3490015
cites work: Line Digraph Iterations and the (d, k) Digraph Problem
cites work: Q5616727
cites work: Q5629652
cites work: Q4079637
cites work: Q3356329
cites work: Sufficient conditions for maximally connected dense graphs
full work available at URL: 0012-365x(94)90157-0
OpenAlex ID: W2051244399
description: scientific article; zbMATH DE number 562660