Upper k-Star-Forming Sets, k-Independence, and Upper Domination
Abstract
For a positive integer k, let βk(G) be the maximum cardinality of a vertex set inducing maximum degree less than k, and let SFk(G) be the maximum cardinality of a minimal k-star-forming set. The known inequality βk(G)≤ SFk(G) suggests asking when equality holds. We place this question in the framework of upper domination: at k=1, β1(G)=α(G) and SF1(G)=Γ(G), so the classical equality Γ=α 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(Ka,b)=SFk(Ka,b)=max{a,b,2k−2} (a,b≥ k), and record the elementary low-degree case Δ(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 β2(G)=SF2(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≥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 Γ, β2, and SF2. In particular, Γ=β2 on every even-by-even rectangular grid, while β2≤ SF2 always; this motivates a grid equality conjecture whose even-by-even case would yield a three-parameter identity.
Related
- An improved upper bound for the fair domination number of maximal outerplanar graphs
- An improved lower and upper bound of the k-limited domination number
- A new upper bound for Sidon sets in 𝔽24k+3
- An Improved Upper Bound for Finite Sidon Sets via Vector-Valued Smoothing
- Cardinalities of Jordan Diophantine sets of upper triangular integer matrices
BibTeX
@misc{sahbi2026upper,
title = {{Upper $k$-Star-Forming Sets, $k$-Independence, and Upper Domination}},
author = {Rafik Sahbi},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.03785},
eprint = {2610.03785},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.03785},
}
RIS
TY - UNPB
TI - Upper k-Star-Forming Sets, k-Independence, and Upper Domination
AU - Rafik Sahbi
PY - 2026
DA - 2026/10/27
PB - arXiv
DO - 10.48550/arxiv.2610.03785
UR - https://arxiv.org/abs/2610.03785
AB - For a positive integer k, let β_k(G) be the maximum cardinality of a vertex set inducing maximum degree less than k, and let SF_k(G) be the maximum cardinality of a minimal k-star-forming set. The known inequality β_k(G)≤ SF_k(G) suggests asking when equality holds. We place this question in the framework of upper domination: at k=1, β_1(G)=α(G) and SF_1(G)=Γ(G), so the classical equality Γ=α 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} (a,b≥ k), and record the elementary low-degree case Δ(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 β_2(G)=SF_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≥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 Γ, β_2, and SF_2. In particular, Γ=β_2 on every even-by-even rectangular grid, while β_2≤ SF_2 always; this motivates a grid equality conjecture whose even-by-even case would yield a three-parameter identity.
ER -