PulseExploreJournal ClubDebatesTrendingResearchersJournals
Instagram
HomeExploreJournal ClubTrending
Synapse
⌘+K
Synapse
August 8, 20260 citationsOpen Access

Exact Support-Four Labelings of 3-Uniform 3-Regular Hypergraphs

View Full Paper
KHKyoungheon Hong

Key Points

  • The aim is to prove that every finite 3-uniform 3-regular hypergraph has four transversals, displaying a specific labeling property.
  • Reduced the non-2-colorable case to det-extremal cubic bipartite incidence graphs.
  • Utilized the Heawood vertex-sum characterization and a finite Local Fano theorem.
  • Applied cactus decomposition with a Property-B theorem for simple cubic bipartite graphs.
  • Every finite connected simple cubic graph has four total dominating sets, each vertex contained exactly twice.
  • The proof involves 18,939,904 exact boundary instances certified by a reproducible certificate route.
  • Connectivity two cases were resolved using a shared-endpoint marker gluing argument.

Abstract

We prove that every finite 3-uniform 3-regular hypergraph has four transversals such that every vertex belongs to exactly two of them. Equivalently, every such hypergraph admits a labeling by the six two-element subsets of 4 whose labels cover 4 on every edge. This answers Question 39 in the published version of Goddard and Henning’s paper (Question 38 in the arXiv version). As a consequence, every finite connected simple cubic graph has four total dominating sets containing each vertex exactly twice. The proof reduces the non-2-colorable case to det-extremal cubic bipartite incidence graphs. The 3-connected case is treated through the Heawood vertex-sum characterization and a finite Local Fano theorem. The latter consists of 18,939,904 exact boundary instances and is certified by a reproducible certificate route and a certificate-independent exhaustive search using no symmetry reduction. For connectivity two, we combine the Funk–Jackson–Labbate–Sheehan cactus decomposition with an incidence-separating Property-B theorem for simple cubic bipartite graphs that are Pfaffian but non-det-extremal and a shared-endpoint marker gluing argument. This manuscript is a preprint and has not undergone formal peer review.

Ask AI
Helpful
Bookmark
Share
View Full Paper

Cite This Study

Kyoungheon Hong (2026) studied this question.

synapsesocial.com/papers/6a76db12f12abadc7981607chttps://doi.org/10.5281/zenodo.21819480
Ask AI
Helpful
Bookmark
Share
View Full Paper