@Article{Cichacz2026,
author = "Cichacz, Sylwia and Görlich, Agnieszka and Suchan, Karol",
title = "Minimum k-critical-bipartite graphs: the irregular case",
journal = "Opuscula Math.",
year = "2026",
volume = "46",
number = "2",
pages = "201--218",
doi = "https://doi.org/10.7494/OpMath.202602181",
url = "https://doi.org/10.7494/OpMath.202602181",
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",
issn = "1232-9274"
}