×

On the lower bound of \(k\)-maximal digraphs. (English) Zbl 1339.05162

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.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C35 Extremal problems in graph theory
05C40 Connectivity
PDFBibTeX XMLCite
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.