Lin, Xiaoxia; Fan, Suohai; Lai, Hong-Jian; Xu, Murong On the lower bound of \(k\)-maximal digraphs. (English) Zbl 1339.05162 Discrete Math. 339, No. 10, 2500-2510 (2016). Summary: For a digraph \(D\), let \(\lambda(D)\) be the arc-strong-connectivity of \(D\). For an integer \(k > 0\), a simple digraph \(D\) with \(| V(D) | \geq k + 1\) is \(k\)-maximal if every subdigraph \(H\) of \(D\) satisfies \(\lambda(H) \leq k\) but for adding new arc to \(D\) results in a subdigraph \(H^\prime\) with \(\lambda(H^\prime) \geq k + 1\). We prove that if \(D\) is a simple \(k\)-maximal digraph on \(n > k + 1 \geq 2\) vertices, then \[ | A(D) | \geq \binom{n}{2} +(n - 1) k + \left\lfloor \frac{n}{k + 2} \right\rfloor \left(1 + 2 k - \binom{k + 2}{2}\right) . \] This bound is best possible. Furthermore, all extremal digraphs reaching this lower bound are characterized. Cited in 5 Documents MSC: 05C20 Directed graphs (digraphs), tournaments 05C35 Extremal problems in graph theory 05C40 Connectivity Keywords:strong arc connectivity; maximum subdigraph arc connectivity; extremal digraphs PDFBibTeX XMLCite \textit{X. Lin} et al., Discrete Math. 339, No. 10, 2500--2510 (2016; Zbl 1339.05162) Full Text: DOI References: [2] Bang-Jensen, J.; Gutin, G., Digraphs: Theory, Algorithms and Applications (2009), Springer-Verlag: Springer-Verlag London · Zbl 1170.05002 [3] Bondy, J. A.; Murty, U. S.R., Graph Theory (2008), Springer: Springer New York · Zbl 1134.05001 [4] Lai, H.-J., The size of strength-maximal graphs, J. Graph Theory, 14, 187-197 (1990) · Zbl 0756.05071 [5] Mader, W., Minimale n-fach kantenzusammenhïngende Graphen, Math. Ann., 191, 21-28 (1971) · Zbl 0198.29202 [6] Matula, D. W., The cohesive strength of graphs, (Chartrand, G.; Kapoor, S. F., The Many Faces of Graph Theory, Lecture Notes in Mathematics, vol. 110 (1969), Springer-Verlag: Springer-Verlag berlin), 215-221 · Zbl 0196.27204 [7] Matula, D., \(K\)-components, clusters, and slicings in graphs, SIAM J. Appl. Math., 22, 459-480 (1972) · Zbl 0243.05111 [8] Matula, D. W., Subgraph connectivity number of a graph, (Chartrand, G.; Kapoor, S. F., Theorey and Applications of Graphs, Lecture Notes in Mathematics, vol. 642 (1976), Springer-Verlag: Springer-Verlag berlin), 371-383 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.