Vadim E. Levit

Vadim E. Levit, Eugen Mandrescu, Kevin Pereyra

Let $G$ be a finite simple graph. An independent set $I$ of $G$ is critical if $\left|I\right|-\left|N(I)\right|\ge\left|J\right|-\left|N(J)\right|$ for every independent set $J$ of $G$. A critical independent set is maximum if it has maximum cardinality. The $core$ and the $nucleus$ of $G$ are defined as the intersection of all maximum independent sets and the intersection of all maximum critical independent sets, respectively. In 2019, Jarden, Levit, and Mandrescu posed the problem of characterizing the graphs satisfying $core(G)=nucleus(G)$. In this paper, we provide a complete solution to this problem. Using Larson's independence decomposition, which partitions any graph into a König--Egerváry component $L_G$ an a $2$-bicritical component $L_G^c$, we establish that $core(G)=nucleus(G)$ holds if and only if $core ({L_G^c})=\emptyset$ and no vertex of $corona(G)$ lies in the boundary between $L_G$ and $L_G^c$. We also show that the same boundary condition is equivalent to the identity $diadem(G)=corona(G) \cap L(G)$. Several consequences and related structural properties are also derived.

Vadim E. Levit, Eugen Mandrescu

It was proved in (Levit and Mandrescu, 2022) that both $(V(G), Crown(G))$ and $(V(G), CritIndep(G))$ are augmentoids, established partial augmentation phenomena for the family $Ψ(G)$ of local maximum independent sets, and asked in Problem~5.5 to characterize the graphs whose family $Ψ(G)$ is an augmentoid. We prove that the answer is positive in full generality: for every finite simple graph $G$, the set system $(V(G),Ψ(G))$ is an augmentoid. The proof is constructive. If $S,T\inΨ(G)$, then the explicit choice \[ A=S \setminus N[T],\qquad B=T \setminus N[S] \] satisfies \[ T\cup A\inΨ(G),\qquad S\cup B\inΨ(G),\qquad |T\cup A|=|S\cup B|. \] As a structural consequence, for every fixed $S\inΨ(G)$ the map $T\mapsto S\cup T$ induces a canonical bijection from $Ψ(G-N[S])$ onto the members of $Ψ(G)$ containing $S$, and \[ α(G)=|S|+α(G-N[S]). \] This decomposition also yields explicit formulas for the intersection and the union of all the maximum independent sets extending $S$, together with counting formulas for the local maximum and maximum independent sets containing $S$. We also add a short visual guide to the framework $CritIndep(G) \subseteq Crown(G)\subseteq Psi(G)$ and end with several natural follow-up problems suggested by the theorem.

Vadim E. Levit, Ohr Kadrawi

We develop a family-based route to unicyclic graphs whose independence polynomials are unimodal but not log-concave. The paper is organized around one flagship statement: for the explicit KL-closure family $U_{k,r}$, with $r\in\{0,1,2\}$ and admissible $k$, the independence polynomial is unimodal but not log-concave. The proof separates the closure polynomial into a dominant convolution term and a real-rooted correction term. On the non-log-concavity side, we prove symbolically that the penultimate log-concavity inequality fails for every admissible parameter. On the unimodality side, we prove that the main convolution term $H_{k,r}=G_kF_{k+r}$ is unimodal with a controlled mode, using a combination of exact coefficient formulas, Ibragimov's strong-unimodality principle, and a residue-class growth argument. Darroch localization and an adjacent-mode bridge lemma then transfer that mode statement to the full KL closure polynomial. This yields an explicit infinite family of unicyclic graphs with unimodal but non-log-concave independence polynomials. In the exact range $k\le 400$, we further verify that the penultimate break is unique and determine exact mode formulas for $H_{k,r}$, the binomial correction term, and $I(U_{k,r};x)$ itself. The paper also places the KL family inside a broader reservoir program involving Galvin, Ramos-Sun, and Bautista-Ramos trees, from which we obtain substantial universal exact theorems for finite ranges.