EUVIMEDEUVIMED entdecken
Crossref

New Structural Bounds for ker G and core G

Kevin Pereyra

Utilitas Mathematica · 22.07.2026 · 128 · 33-49

DOI: 10.61091/um128-02 ↗

Kurz gefasst

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

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Let \(\alpha(G)\), \(\mu(G)\) and prk\((G)\) denote the independence number, the matching number and the permanental rank of \(G\), respectively. Here prk\((G)\) is the maximum order of a principal submatrix with nonzero permanent of the adjacency matrix of \(G\). Let \(d(G)=\max_{S\subseteq V(G)}\{|S|-|N(S)|\}\) be the critical difference of \(G\). Let core\((G)\) and ker\((G)\) be the intersection of all maximum independent sets and all critical independent sets, respectively. In this note we use Larson’s critical independence decomposition to split the graph into two induced subgraphs, \(L_G\) and \(L_G^c\), where \(L_G\) is Kőnig–Egerváry and \(L_G^c\) is 2-bicritical. We prove that for every graph \(G\) one has \(\alpha(G)-\mu(G) = |L_G|-prk(L_G)+\alpha(L_G^c)-\mu(L_G^c) = d(L_G)+\alpha(L_G^c)-\mu(L_G^c).\) Moreover, we show that \(\alpha(L_G^c)\le \mu(L_G^c)\) and establish the refined kernel bound \(d(L_G)+k\le |ker(G)|,\) where \(k\) is the number of nontrivial connected components of \(L_G\) without a perfect matching. Consequently, \(\alpha(G)-\mu(G)+k\le |ker(G)|.\) In particular, when \(\alpha(G)>\mu(G)\), one has \(|L_G|>prk(L_G)\). The bound is sharp for every prescribed value of \(k\). Since ker\((G)\subseteq core(G)\) for every graph, we recover as a consequence the known Boros–Golumbic–Levit inequality \(\alpha(G)-\mu(G)+1\le |core(G)|\) for connected graphs with at least two vertices and \(\alpha(G)>\mu(G)\). This result improves on related results by Hammer et al. (1982) and by Levit and Mandrescu (1999).

Zitieren

APA

Pereyra, K. (2026). New Structural Bounds for ker G and core G. Utilitas Mathematica, 128, 33-49. https://doi.org/10.61091/um128-02

Vancouver

Pereyra K. New Structural Bounds for ker G and core G. Utilitas Mathematica. 2026;128:33-49. doi:10.61091/um128-02

BibTeX
@article{Pereyra2026,
  author = {Pereyra, Kevin},
  title = {New Structural Bounds for ker G and core G},
  journal = {Utilitas Mathematica},
  year = {2026},
  volume = {128},
  pages = {33--49},
  doi = {10.61091/um128-02}
}
Kostenlos starten →