EUVIMEDEUVIMED entdecken
Crossref

Minimum k-critical-bipartite graphs: the irregular case

Sylwia Cichacz, Agnieszka Görlich, Karol Suchan

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →