TY  - JOUR
ID  - Cichacz2026
LB  - Cichacz2026
AU  - Cichacz, Sylwia
AU  - Görlich, Agnieszka
AU  - Suchan, Karol
TI  - Minimum k-critical-bipartite graphs: the irregular case
ST  - Minimum k-critical-bipartite graphs: the irregular case
JO  - Opuscula Math.
JA  - Opuscula Math.
JF  - Opuscula Mathematica
PY  - 2026
VL  - 46
IS  - 2
SP  - 201
EP  - 218
DO  - https://doi.org/10.7494/OpMath.202602181
UR  - https://doi.org/10.7494/OpMath.202602181
AB  - 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.
KW  - fault-tolerance
KW  - interconnection network
KW  - bipartite graph
KW  - complete matching
KW  - algorithm
KW  - \(k\)-critical-bipartite graph
SN  - 1232-9274
ER  -