Minimum k-critical-bipartite graphs: the irregular case
Opuscula Mathematica · 2026 · 201-218
DOI: 10.7494/opmath.202602181 ↗Kurz gefasst
Fachartikel in der Zeitschrift Opuscula Mathematica, 2026. Verfasst von Sylwia Cichacz und 2 weiteren Autor:innen. Die Arbeit nennt 20 Literaturangaben.
Abstract (Originalsprache)
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.
Zitieren
APA
Cichacz, S., Görlich, A., & Suchan, K. (2026). Minimum k-critical-bipartite graphs: the irregular case. Opuscula Mathematica, 201-218. https://doi.org/10.7494/opmath.202602181
Vancouver
Cichacz S, Görlich A, Suchan K. Minimum k-critical-bipartite graphs: the irregular case. Opuscula Mathematica. 2026:201-218. doi:10.7494/opmath.202602181
BibTeX
@article{Cichacz2026,
author = {Cichacz, Sylwia and Görlich, Agnieszka and Suchan, Karol},
title = {Minimum k-critical-bipartite graphs: the irregular case},
journal = {Opuscula Mathematica},
year = {2026},
pages = {201--218},
doi = {10.7494/opmath.202602181}
}
EUVIMED