Upper $k$-Star-Forming Sets, $k$-Independence, and Upper Domination

Abstract

For a positive integer $k$, let ${\beta }_k(G)$ be the maximum cardinality of a vertex set inducing maximum degree less than $k$, and let $S{F}_k(G)$ be the maximum cardinality of a minimal $k$-star-forming set. The known inequality ${\beta }_k(G)\le S{F}_k(G)$ suggests asking when equality holds. We place this question in the framework of upper domination: at $k=1$, ${\beta }_1(G)=\alpha (G)$ and $S{F}_1(G)=\Gamma (G)$, so the classical equality $\Gamma =\alpha$ on bipartite graphs is exactly the first member of the proposed hierarchy. We prove the equality for complete bipartite graphs for every $k$, obtaining \[ β_k(K_{a,b})=SF_k(K_{a,b})=\max\{a,b,2k-2\}\qquad(a,b\ge k), \] and record the elementary low-degree case $\Delta (G)<k$. For $k=2$ we derive certificate restrictions for minimal $2$-star-forming sets in bipartite graphs. For chain graphs we go further: we prove ${\beta }_2(G)=S{F}_2(G)$ and obtain an exact formula for their common value. The proof uses the nested-neighborhood structure together with a classification of witnesses to the indispensability of a high internal-degree vertex. We retain the equality problem for chain graphs as a conjecture only for $k\ge 3$, and formulate the broader bipartite conjecture. We also determine the upper domination number of every rectangular grid and combine it with the known exact dissociation number to compare $\Gamma$, ${\beta }_2$, and $S{F}_2$. In particular, $\Gamma ={\beta }_2$ on every even-by-even rectangular grid, while ${\beta }_2\le S{F}_2$ always; this motivates a grid equality conjecture whose even-by-even case would yield a three-parameter identity.

arXiv commentThe conjectures stated in the manuscript have been disproved