Opuscula Mathematica
Opuscula Math. 46, no. 2 (2026), 201-218

Minimum k-critical-bipartite graphs: the irregular case

Sylwia Cichacz
Agnieszka Görlich
Karol Suchan
Abstract. We study the problem of finding a minimum \(k\)-critical-bipartite graph of order \((n,m)\): a bipartite graph \(G=(U,V;E)\), with \(|U|=n\), \(|V|=m\), and \(n\gt m\gt 1\), which is \(k\)-critical-bipartite, and the tuple \((|E|, \Delta_U, \Delta_V)\), where \(\Delta_U\) and \(\Delta_V\) denote the maximum degree in \(U\) and \(V\), respectively, is lexicographically minimum over all such graphs. \(G\) is \(k\)-critical-bipartite if deleting any set of at most \(k=n-m\) vertices from \(U\) yields \(G'\) that has a complete matching, i.e., a matching of size \(m\). Cichacz and Suchan solved the problem for biregular bipartite graphs. Here, we extend their results to bipartite graphs that are not biregular. We prove tight lower bounds on the connectivity of \(k\)-critical-bipartite graphs, and we show that \(k\)-critical-bipartite graphs are expander graphs.
Keywords: fault-tolerance, interconnection network, bipartite graph, complete matching, algorithm, \(k\)-critical-bipartite graph.
Mathematics Subject Classification: 05C35, 05C70, 05C85, 68M10, 68M15.
Full text (pdf)
References ▼
  1. [1] B. Afshar-Nadjafi, Multi-skilling in scheduling problems: A review on models, methods and applications, Comput. Ind. Eng. 151 (2021), 107004. https://doi.org/10.1016/j.cie.2020.107004
  2. [2] S. Attali, M. Parter, D. Peleg, S. Solomon, Wireless expanders, Proc. of the 30th on Symposium on Parallelism in Algorithms and Architectures (SPAA), Association for Computing Machinery, 2018, 13-22. https://doi.org/10.1145/3210377.3210396
  3. [3] L.A. Bassalygo, M.S. Pinsker, The complexity of an optimal non-blocking communication scheme without reorganization, Problemy Peredachi Informatsii 9 (1973), 84-87.
  4. [4] S. Cichacz, K. Suchan, Minimum \(k\)-critical bipartite graphs, Discrete Appl. Math. 302 (2021), 54-66. https://doi.org/10.1016/j.dam.2021.06.005
  5. [5] S. Cichacz, A. Görlich, K. Suchan, \(k\)-fault-tolerant graphs for \(p\) disjoint complete graphs of order \(c\), Discuss. Math. Graph Theory 44 (2024), 1471-1484. https://doi.org/10.7151/dmgt.2504
  6. [6] C. Crespelle, P.G. Drange, F.V. Fomin, P. Golovach, A survey of parameterized algorithms and the complexity of edge modification, Comput. Sci. Rev. 48 (2023), Article no. 100556. https://doi.org/10.1016/j.cosrev.2023.100556
  7. [7] R. Diestel, Graph Theory, Springer, 2017.
  8. [8] O. Favaron, On \(k\)-factor-critical graphs, Discuss. Math. Graph Theory 16 (1996), 41-55. https://doi.org/10.7151/dmgt.1022
  9. [9] Z. Han, Y. Fu, X. Du, Review of the embedding of hypercube and its variants, Proc. 2020 Int. Conf. Cyberspace Innov. Adv. Technol. (CIAT), Association for Computing Machinery, 2021, 330-334.
  10. [10] J.P. Hayes, A graph model for fault-tolerant computing systems, IEEE Trans. Computers C-25 (1976), 875-884. https://doi.org/10.1109/tc.1976.1674712
  11. [11] P. Laroche, F. Marchetti, S. Martin, Z. Róka, Bipartite complete matching vertex interdiction problem: Application to robust nurse assignment, Proc. 2014 Int. Conf. Control, Decision Inf. Technol. (CoDIT), Institute of Electrical and Electronics Engineers, 2014, 182-187. https://doi.org/10.1109/codit.2014.6996890
  12. [12] Y. Li, Z. Nie, A note on \(n\)-critical bipartite graphs and its application, Proc. 3rd Conf. Combinatorial Optim. Appl. (COCOA), Springer, 2009, 279-286. https://doi.org/10.1007/978-3-642-02026-1_26
  13. [13] N. Linial, Expander graphs and their applications, Proc. Natl. Acad. Sci. USA 43 (2006), 439-561.
  14. [14] L. Lovász, On the structure of factorizable graphs, Acta Math. Hungar. 23 (1972), 179-195. https://doi.org/10.1007/bf01889914
  15. [15] H. Shen, Y. Liang, Z.-J.M. Shen, C.-P. Teo, Reliable flexibility design of supply chains via extended probabilistic expanders, Prod. Oper. Manag. 28 (2019), 700-720. https://doi.org/10.1111/poms.12942
  16. [16] J.C. Smith, Y. Song, A survey of network interdiction models and algorithms, Eur. J. Oper. Res. 283 (2020), 797-811. https://doi.org/10.1016/j.ejor.2019.06.024
  17. [17] S. Wang, X. Wang, J. Zhang, A review of flexible processes and operations, Prod. Oper. Manag. 30 (2021), 1804-1824. https://doi.org/10.1111/poms.13101
  18. [18] D.B. West, Introduction to Graph Theory, Prentice Hall, 2001.
  19. [19] Q. Yu, Characterizations of various matching extensions in graphs, Australas. J. Comb. 7 (1993), 55-64.
  20. [20] Z. Zhang, X. Zhang, D. Lou, X. Wen, Minimum size of \(n\)-factor-critical graphs and \(k\)-extendable graphs, Graphs Comb. 28 (2012), 433-448. https://doi.org/10.1007/s00373-011-1045-y
About the authors ▼
Sylwia Cichacz
https://orcid.org/0000-0002-7738-0924
AGH University of Krakow, Faculty of Applied Mathematics, Al. A. Mickiewicza 30, 30-059 Krakow, Poland
Agnieszka Görlich (corresponding author)
https://orcid.org/0000-0002-7198-0531
AGH University of Krakow, Faculty of Applied Mathematics, Al. A. Mickiewicza 30, 30-059 Krakow, Poland
Karol Suchan
https://orcid.org/0000-0003-0793-0924
Universidad Diego Portales, Facultad de Ingeniería y Ciencias, Av. Ejército Libertador 441, 8370191 Santiago, Chile; AGH University of Krakow, Faculty of Applied Mathematics, Al. A. Mickiewicza 30, 30-059 Krakow, Poland
About the article ▼
Communicated by Dalibor Fronček.
Received: 2025-03-14.
Revised: 2025-12-20.
Accepted: 2026-02-18.
Published online: 2026-04-10.
Cite this article as ▼
Sylwia Cichacz, Agnieszka Görlich, Karol Suchan, Minimum k-critical-bipartite graphs: the irregular case, Opuscula Math. 46, no. 2 (2026), 201-218, https://doi.org/10.7494/OpMath.202602181.
Download this article's citation as: