Abstract
Boesch and McHugh in [J. Combinatorial Theory Ser. B 38 (1985), 1-7] introduced the edge-maximal \((k, \ell )\)-graphs to study of network subcohesion, and obtained best possible upper size bounds for all edge-maximal \((k, \ell )\)-graphs. The best possible lower bounds are obtained in [J. Graph Theory 18 (1994), 227-240]. Let \(k,\ell > 0\) be integers. A strict digraph D is a \((k,\ell )\)-digraph if for any subdigraph H of D, that \(|V(H)|\ge \ell\) implies \(\lambda (H)\le k-1\). An arc-maximal \((k,\ell )\)-digraph D is one such that for any \(e\in A(D^c)\), \(D+e\) is not a \((k,\ell )\)-digraph. We show that there is a close relationship between the extremal edge-maximal \((k,\ell )\)-graphs and the extremal arc-maximal \((k,\ell )\)-digraphs. This is applied to determine the optimal upper and lower bounds of the sizes of an arc-maximal \((k,\ell )\)-digraphs. Moreover, the arc-maximal \((k,\ell )\)-digraphs reaching the lower bounds and the upper bounds are respectively characterized.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Data Availability Statement
Data sharing not applicable to this article as no datasets were generated or analysed during the current study.
References
Anderson, J., Lai, H.-J., Lin, X., Xu, M.: On \(k\)-maximal strength digraphs. J. Graph Theory 84, 17–25 (2017)
Bang-Jensen, J., Gutin, G.: Digraphs: Theory, Algorithms and Applications, 2nd edn. Springer-Verlag, London (2009)
Boesch, F.T., McHugh, J.A.M.: An edge extremal result for subcohesion. J. Combinatorial Theory Ser.B 38 (1985), 1-7
Bollobás, B.: Extremal Graph Theory. London Math. Soc. Monographs, Vol. 11, Academic Press, London, (1978)
Bondy, J.A., Murty, U.S.R.: Graph Theory. Springer, New York (2008)
Lai, H.-J.: The size of strength-maximal graphs. J. Graph Theory 14, 187–197 (1990)
Lai, H.-J., Zhang, C.: Edge-maximal \((k, l)\)-graphs. J. Graph Theory 18, 227–240 (1994)
Lin, X., Fan, S., Lai, H.-J., Xu, M.: On the lower bound of \(k\)-maximal digraphs. Discrete Math. 339, 2500–2510 (2016)
Mader, W.: Minimale \(n\)-fach kantenzusammenhngende graphen. Math. Ann. 191, 21–28 (1971)
Matula, D.W.: The cohesive strength of graphs, The Many Faces of Graph Theory, Lecture Notes in Mathematics, No. 110, G. Chartrand and S. F. Kapoor eds., Springer-Verlag, berlin, pp. 215-221 (1969)
Matula, D.: \(K\)-components, clusters, and slicings in graphs. SIAM J. Appl. Math. 22, 459–480 (1972)
Matula, D.W.: Subgraph connectivity number of a graph, Theorey and Applications of Graphs, Lecture Notes in Mathematics, No. 642, G. Chartrand and S. F. Kapoor eds., Springer-Verlag,
Tian, Y., Lai, H.-J., Meng, J.: On the sizes of vertex-\(k\)-maximal \(r\)-uniform hypergraphs. Graphs Combin. 35, 1001–1010 (2019)
Turán, P.: Eine Extremal aufgabe aus der Graphentheorie. Mat. Fiz. Lapok 48, 436–452 (1941)
Acknowledgements
The research is supported in part by National Natural Science Foundation of China (11301217, 11861066, 61572010) and Natural Science Foundation of Fujian Province, China (No.2021J01860).
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Xu, L., Lai, HJ., Tian, Y. et al. The Extremal Sizes of Arc-Maximal (k, l)-Digraphs. Graphs and Combinatorics 38, 72 (2022). https://doi.org/10.1007/s00373-022-02468-0
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s00373-022-02468-0
Keywords
- Maximum subgraph edge-connectivity
- Arc-strong connectivity
- Maximum subdigraph arc-strong connectivity
- \(((k,\, \ell ) )\)-digraphs