Upper $k$-Star-Forming Sets, $k$-Independence, and Upper Domination
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)\le 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 \[…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.03785
curl -X POST /api/v1/records/arxiv/2610.03785/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.03785/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'