EUVIMEDEUVIMED entdecken
Crossref

A core–corona characterization of König–Egerváry graphs

Kevin Pereyra

Utilitas Mathematica · 22.07.2026 · 128 · 51-66

DOI: 10.61091/um128-03 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Utilitas Mathematica, online erschienen am 22.07.2026. Verfasst von Kevin Pereyra.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Several necessary properties of König–Egerváry graphs involving the core, the corona, and critical independent sets are by now part of the folklore of the theory, and have motivated different lines of research within the same framework. In particular, every König–Egerváry graph satisfies the core–corona identity \(|core(G)|+|corona(G)|=2\alpha(G),\) the covering relation \(corona(G)cup N(core(G))=V(G),\) and the fact that \(core(G)\) is a critical independent set. Each of these conditions captures a different aspect of the interaction between maximum independent sets and matchings, but none of them alone characterizes the König–Egerváry property. In this note we show that their conjunction does: a graph \(G\) is König–Egerváry if and only if the above two core–corona conditions hold and \(core(G)\) is critical. Equivalently, the class of König–Egerváry graphs is precisely the intersection of the three graph families determined by these conditions. We also provide examples showing that the characterization is sharp: any two of the three conditions may hold in a graph which is not König–Egerváry.

Zitieren

APA

Pereyra, K. (2026). A core–corona characterization of König–Egerváry graphs. Utilitas Mathematica, 128, 51-66. https://doi.org/10.61091/um128-03

Vancouver

Pereyra K. A core–corona characterization of König–Egerváry graphs. Utilitas Mathematica. 2026;128:51-66. doi:10.61091/um128-03

BibTeX
@article{Pereyra2026,
  author = {Pereyra, Kevin},
  title = {A core–corona characterization of König–Egerváry graphs},
  journal = {Utilitas Mathematica},
  year = {2026},
  volume = {128},
  pages = {51--66},
  doi = {10.61091/um128-03}
}
Kostenlos starten →