Opuscula Math. 46, no. 2 (2026), 201-218
https://doi.org/10.7494/OpMath.202602181

 
Opuscula Mathematica

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)

  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. 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. 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. 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. 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. 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. R. Diestel, Graph Theory, Springer, 2017.
  8. O. Favaron, On \(k\)-factor-critical graphs, Discuss. Math. Graph Theory 16 (1996), 41-55. https://doi.org/10.7151/dmgt.1022
  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. 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. 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. 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. N. Linial, Expander graphs and their applications, Proc. Natl. Acad. Sci. USA 43 (2006), 439-561.
  14. L. Lovász, On the structure of factorizable graphs, Acta Math. Hungar. 23 (1972), 179-195. https://doi.org/10.1007/bf01889914
  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. 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. 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. D.B. West, Introduction to Graph Theory, Prentice Hall, 2001.
  19. Q. Yu, Characterizations of various matching extensions in graphs, Australas. J. Comb. 7 (1993), 55-64.
  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
  • Karol Suchan
  • ORCID iD 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
  • Communicated by Dalibor Fronček.
  • Received: 2025-03-14.
  • Revised: 2025-12-20.
  • Accepted: 2026-02-18.
  • Published online: 2026-04-10.
Opuscula Mathematica - cover

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:
a .bib file (BibTeX),
a .ris file (RefMan),
a .enw file (EndNote)
or export to RefWorks.

We advise that this website uses cookies to help us understand how the site is used. All data is anonymized. Recent versions of popular browsers provide users with control over cookies, allowing them to set their preferences to accept or reject all cookies or specific ones.