On graphs with equal total domination and Grundy total domination number
Pith reviewed 2026-05-25 13:47 UTC · model grok-4.3
The pith
Regular bipartite graphs with equal total and Grundy total domination number 6 are characterized by a correspondence to certain finite projective planes.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The main result of the paper is a characterization of regular bipartite graphs with γ_t(G)=γ_gr^t(G)=6 proved by establishing a surprising correspondence between existence of such graphs and a classical but still open problem of the existence of certain finite projective planes.
What carries the argument
The correspondence between regular bipartite graphs with γ_t(G)=γ_gr^t(G)=6 and certain finite projective planes.
If this is right
- Existence of regular bipartite graphs with γ_t=γ_gr^t=6 is equivalent to existence of the corresponding projective planes.
- Known projective planes produce explicit examples of graphs satisfying the equality.
- Absence of such planes implies absence of such graphs.
- The equality condition for these graphs reduces directly to the plane existence question.
Where Pith is reading between the lines
- Open questions about projective planes can be rephrased as questions about lengths of dominating sequences in graphs.
- The method might extend to characterize equality at other fixed values or in other graph families.
- Small known planes could be used to build concrete graph examples for further study of sequence properties.
Load-bearing premise
The established correspondence between regular bipartite graphs with γ_t(G)=γ_gr^t(G)=6 and certain finite projective planes is bijective and relies only on the combinatorial properties of total dominating sequences.
What would settle it
A regular bipartite graph with γ_t(G)=γ_gr^t(G)=6 that does not correspond to any finite projective plane of the relevant order, or a projective plane without a corresponding graph that satisfies the equality.
Figures
read the original abstract
A sequence $(v_1,\ldots ,v_k)$ of vertices in a graph $G$ without isolated vertices is called a total dominating sequence if every vertex $v_i$ in the sequence totally dominates at least one vertex that was not totally dominated by $\{v_1,\ldots , v_{i-1}\}$ and $\{v_1,\ldots ,v_k\}$ is a total dominating set of $G$. The length of a shortest such sequence is the total domination number of G ($\gamma_t(G)$), while the length of a longest such sequence is the Grundy total domination number of $G$ ($\gamma_{gr}^t(G)$). In this paper we study graphs with equal total and Grundy total domination number. We characterize bipartite graphs with both total and Grundy total domination number equal to 4, and show that there is no connected chordal graph $G$ with $\gamma_t(G)=\gamma_{gr}^t(G)=4$. The main result of the paper is a characterization of regular bipartite graphs with $\gamma_t(G)=\gamma_{gr}^t(G)=6$ proved by establishing a surprising correspondence between existence of such graphs and a classical but still open problem of the existence of certain finite projective planes.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper defines total dominating sequences in graphs without isolated vertices and studies the equality γ_t(G) = γ_gr^t(G). It characterizes all bipartite graphs achieving this equality at 4, proves there are no connected chordal graphs with the equality at 4, and gives a characterization of regular bipartite graphs with the equality at 6 by establishing a correspondence between the existence of such graphs and the existence of certain finite projective planes.
Significance. If the correspondence is bijective and correctly established from the combinatorial properties of total dominating sequences, the main result is significant: it reduces the graph-theoretic question to a classical open problem in finite projective geometry, providing an explicit link between the two areas. The explicit characterization for value 4 supplies concrete structural descriptions that may aid further enumeration or algorithmic work.
minor comments (3)
- [Abstract] The abstract refers to 'a surprising correspondence' with finite projective planes but does not name the precise order or parameters of the planes; adding this detail would improve immediate readability.
- [Characterization of bipartite graphs with γ_t = γ_gr^t = 4] In the section treating the =4 case for bipartite graphs, the proof of the characterization would benefit from an explicit small example (e.g., the smallest graph achieving equality) to illustrate the sequence construction.
- Notation for total dominating sequences is introduced clearly, but a short table comparing γ_t and γ_gr^t values across the characterized families would help readers verify the equality claims at a glance.
Simulated Author's Rebuttal
We thank the referee for the careful reading, positive significance assessment, and recommendation of minor revision. No specific major comments appear in the report, so we have no individual points requiring rebuttal or clarification at this stage. We will prepare a revised version incorporating any minor editorial changes needed to address the overall recommendation.
Circularity Check
No significant circularity; result maps to external open problem
full rationale
The paper's central claim is a characterization of regular bipartite graphs with γ_t(G)=γ_gr^t(G)=6 obtained by exhibiting an explicit bijection to the existence of certain finite projective planes. This reduces the graph-theoretic question to an independent, long-standing open problem in combinatorial geometry rather than deriving the equality from any internal fit, self-definition, or self-citation chain. The separate treatment of the =4 case for bipartite graphs is likewise self-contained and does not invoke the projective-plane correspondence. No load-bearing step reduces by construction to its own inputs; the derivation is therefore externally falsifiable and non-circular.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math Standard definitions and properties of total dominating sequences, total domination number γ_t(G), and Grundy total domination number γ_gr^t(G) in graphs without isolated vertices.
Reference graph
Works this paper leans on
-
[1]
B. Breˇ sar, Cs. Bujt´ as, T. Gologranc, S. Klavˇ zar, G. Koˇ smrlj, B. Patk´ os, Zs. Tuza, M. Vizer, On Grundy total domination number in product g raphs, Discuss. Math. Graph Theory, to appear. 11
-
[2]
B. Breˇ sar, M. A. Henning, D. F. Rall, Total dominating sequence s in graphs, Discrete. Math. 339 (2016) 1665–1676
work page 2016
-
[3]
B. Breˇ sar, T. Kos, G. Nasini, P. Torres, Total dominating sequ ences in trees, split graphs, and under modular decomposition, Discrete Op tim. 28 (2018) 16–30
work page 2018
-
[4]
E. J. Cockayne, R. M. Dawes, S. T. Hedetniemi, Total domination in graphs, Networks 10 (1980) 211–219
work page 1980
-
[5]
G. A. Dirac, On rigid circuit graphs, Abhandlungen aus dem Mathem atis- chen Seminar der Universit¨ at Hamburg 25(1–2) (1961) 71–76
work page 1961
-
[6]
M. A. Henning, S. Klavˇ zar, D. F. Rall, Total version of the domina tion game, Graphs Combin. 31(5) (2015) 1453–1462
work page 2015
-
[7]
M. A. Henning, D. F. Rall, Trees with equal total domination and ga me total domination numbers, Discrete Appl. Math. 226 (2017) 58–70
work page 2017
-
[8]
M. A. Henning, A. Yeo, Total domination in graphs (Springer Mono graphs in Mathematics), ISBN-13: 978-1461465249 (2013)
work page 2013
-
[9]
D. R. Stinson, Combinatorial designs: constructions and analys is, Springer Science & Business Media (2007)
work page 2007
-
[10]
M. J. Nadjafi-Arani, M. H. Siggers, H. Soltani, Characterisatio n of forests with trivial game domination numbers, J. Comb. Optim. 32(3) (2016) 800– 811. 12
work page 2016
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.