On the order and size of \(s\)-geodetic digraphs with given connectivity
type: Item
instance of: scholarly article
title: On the order and size of \(s\)-geodetic digraphs with given connectivity
zbMATH Open document ID: 0886.05086
DOI: 10.1016/S0012-365X(96)00314-7
author: J. Ning
published in: Discrete Mathematics
publication date: 1998-04-08T00:00:00Z
review text: A digraph \(G\) without cycles of length at most \(s\) is said to be \(s\)-geodetic if for any two different vertices \(x,y\), there is at most one \(x\)--\(y\) path of length not exceeding \(s\). The authors are interested in the maximum integer \(s\) for which \(G\) is \(s\)-geodetic. Some recent results [see, e.g., \textit{M. A. Fiol}, J. Graph Theory 17, 31-45 (1993; Zbl 0783.05054)] show that if the order \(n\) of a digraph is big enough, then its connectivity \(\kappa\) attains its maximum value. In this paper several such results are derived for \(s\)-geodetic digraphs of a small order. E.g., for \(s\geq 2\), if the minimum degree \(\delta \geq \lceil \root s \of {\frac n2 - 1}\rceil\), then \(\kappa = \delta\). Similar results are given also for the edge-connectivity, superconnectivity and edge-superconnectivity.
reviewed by: Ján Plesník
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 1110072
zbMATH Keywords: connectivity
zbMATH Keywords: edge-connectivity
zbMATH Keywords: superconnectivity
zbMATH Keywords: \(s\)-geodetic digraph
MaRDI profile type: Publication
cites work: Degree realization of undirected graphs in reduced form
cites work: Large fault-tolerant interconnection networks
cites work: A Graph-Theoretic Approach to a Communications Problem
cites work: Maximally connected digraphs
cites work: On super-edge-connected digraphs and bipartite digraphs
cites work: The connectivity of large digraphs and graphs
cites work: Q3490015
cites work: Q5616727
cites work: A property of a-fragments of a digraph
cites work: Sur la séparation dans les graphes de Cayley abéliens
cites work: Vosperian and superconnected abelian Cayley digraphs
cites work: Results on the edge-connectivity of graphs
cites work: Q4041603
cites work: Q3356329
cites work: Sufficient conditions for maximally connected dense graphs
full work available at URL: s0012-365x(96)00314-7
OpenAlex ID: W2025274559
description: scientific article; zbMATH DE number 1110072