×

Distance connectivity in graphs and digraphs. (English) Zbl 0857.05062

Given a digraph of diameter \(D\) and an integer \(t\), \(1\leq t\leq D\), the \(t\)-distance connectivity [edge connectivity] \(\kappa(t)\) \([\lambda(t)]\) of the digraph is the minimum cardinality of a set of vertices [edges] separating two vertices \(x, y\) at distance \(d(x, y)\geq t\). The \(t\)-degree \(\delta(t)\) is the minimum among the out-degrees and in-degrees of all vertices with (out- or in-) eccentricity at least \(t\). Constructions of digraphs with prescribed \(\kappa(t)\), \(\lambda(t)\) and \(\delta(t)\) are given. Also some conditions are presented for a digraph (or bipartite digraph) to be maximally connected (i.e. \(\kappa(t)=\delta(t)\) or \(\lambda(t)=\delta(t)\)).

MSC:

05C40 Connectivity
05C12 Distance in graphs
05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: DOI