{"id":"arxiv/2608.17851","url":"https://arxiv.org/abs/2608.17851","tags":["math.CO"],"score":0,"title":"Counterexamples to two conjectures on (1, 2)-domination in cubic graphs","domain":"math.CO","source":"arxiv","authors":["Martin Knor","Jelena Sedlar","Riste Škrekovski"],"reviews":0,"subject":"math.CO","summary":"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,…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-18","reactions":{}}