Det-extremal cubic graphs and the total domatic number

Abstract

A graph G is det-extremal if |det A|=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 number is $1$. We further show that McCuaig's characterization extends to all $3$-connected cubic graphs, and that every connected det-extremal cubic graph has girth $3$, $5$ or $6$. We also prove that a connected det-extremal cubic non-bipartite graph has at least $28$ vertices, and that this bound is best possible. Through this correspondence, these results carry over to cubic graphs with total domatic number $1$. In addition, in the language of configurations, our results imply that every triangle-free $3$-configuration has a blocking set.

Total Vertex Irregularity Strength of Cubic and 4-Regular Graphs
Songling Shan, Yucheng Zhong
arXiv24 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
A Turán-type extremal problem for the number of spanning trees in C₄-free graphs
Shaohan Xu, Fengming Dong, Kexiang Xu
arXiv28 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Every cubic graph has four total dominating sets covering each vertex at most twice
Hyemin Kwon, Boram Park, Yoshio Sano
arXiv14 Oct 2026PreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
Turán-type extremal problems for unbalanced signed graphs
Linfeng Xie, Keheng Zhu, Xiaogang Liu
arXiv16 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
A Quadratic Lower Bound for the Shield Number of the Stable Marriage Problem: Rearrangement, Extremal Construction, and Biclique Realizability
Yoshiteru Ishida
arXiv1 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{choi2026detextremal,
  title = {{Det-extremal cubic graphs and the total domatic number}},
  author = {Myungho Choi and Hyemin Kwon and Boram Park},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.33902},
  eprint = {2609.33902},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.33902},
  note = {CC BY-NC-ND 4.0},
}

RIS

TY  - UNPB
TI  - Det-extremal cubic graphs and the total domatic number
AU  - Myungho Choi
AU  - Hyemin Kwon
AU  - Boram Park
PY  - 2026
DA  - 2026/09/27
PB  - arXiv
DO  - 10.48550/arxiv.2609.33902
UR  - https://arxiv.org/abs/2609.33902
AB  - A graph G is det-extremal if |det A|=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 number is $1$. We further show that McCuaig's characterization extends to all $3$-connected cubic graphs, and that every connected det-extremal cubic graph has girth $3$, $5$ or $6$. We also prove that a connected det-extremal cubic non-bipartite graph has at least $28$ vertices, and that this bound is best possible. Through this correspondence, these results carry over to cubic graphs with total domatic number $1$. In addition, in the language of configurations, our results imply that every triangle-free $3$-configuration has a blocking set.
ER  -

Abstract

Related

Cite