Counterexamples to two conjectures on (1, 2)-domination in cubic graphs
Let G be a cubic graph of order n. The induced cycles vertex number cind(G) is the largest size of a vertex set that induces a 2-regular subgraph of G. By gamma_1,2(G) we denote the (1,2)-domination number of G. Erves and Tepeh introduced the trilobite graphs T_n, which satisfy gamma_1,2(T_n) > cind(T_n). They stated two conjectures, the first of which says that every cubic graph G with cind(G) >= n/2 + 2 satisfies gamma_1,2(G) cind(G) if and only if G is a trilobite. We show that both conjectures are false. A computer search finds counterexamples that are not trilobites already for n = 18,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.17851
curl -X POST /api/v1/records/arxiv/2608.17851/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.17851/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'