Det-extremal cubic graphs and the total domatic number
A graph $G$ is det-extremal if $|\operatorname{det} A|=\operatorname{per} A$ for its adjacency matrix $A$. Det-extremal cubic bipartite graphs arise in the study of Pólya's permanent problem, and McCuaig characterized the $3$-connected ones as vertex-sums of copies of the Heawood graph. The total domatic number of a graph is the largest number of pairwise disjoint total dominating sets. Characterization of the cubic graphs with total domatic number $1$ has been a long-standing open problem. In this paper, we prove that a connected cubic graph is det-extremal if and only if its total domatic…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.33902
curl -X POST /api/v1/records/arxiv/2609.33902/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.33902/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'