Bounds for the ratio between the independent domination number and the domination number
In this article we present new and improved results for the ratio between the independent domination number and the domination number in graphs with bounded degree. We present a general formula, that, for a fixed maximum degree, allows to compute an upper bound for this ratio as a function of an upper bound $β|V|$ for the independent domination number. We also apply this formula to several known upper bounds for the independent domination number. Furthermore we present constructions giving lower bounds for the best possible upper bound in various classes of graphs with bounded degree.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.16698
curl -X POST /api/v1/records/arxiv/2606.16698/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.16698/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'