Pith. sign in

REVIEW 4 major objections 3 minor 17 references

The $k$-Total Bondage Number of a Graph

T0 review · 4 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper defines the k-total bondage number of a graph and proves exact formulas for paths, cycles, wheels, and complete graphs.

desk verdict The new k-total bondage invariant is worth a footnote, but the advertised exact values for paths and complete graphs are contradicted by small explicit cases. read the letter →

arxiv 2506.07000 v1 pith:ZSBHNSRB submitted 2025-06-08 math.CO

Jean-Pierre Appel , Gabby Fischberg , Kyle Kelley , Nathan Shank , Eliel Sosis This is my paper
classification math.CO MSC 05C69
keywords totaldominationk-totalbondagenumberedgedeletionpathscycleswheelgraphscomplete
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper introduces the k-total bondage number of a graph: the fewest edges whose deletion raises the total domination number by at least k. It proves general bounds, including that deleting one edge can raise total domination by at most 2, then pins down exact values for paths, cycles, wheels, and complete graphs, with upper bounds for complete bipartite graphs and a construction showing that many prescribed values actually occur. The centerpiece is the complete-graph formula, which is quadratic in k and linear in n. If correct, these results give concrete fault-tolerance thresholds in the network model where total domination corresponds to placing transmitters so every node is adjacent to one.

What carries the argument

The central mechanism is the disjoint single-edge component, a copy of P_2 produced by deleting edges. Corollary 2 asserts that among all deletions of i edges from a path, the largest possible total domination number is gamma_t(P_{n-2i}) + 2i, attained by leaving i disjoint copies of P_2 together with one path on n-2i vertices; the paper solves the inequality gamma_t(P_{n-2i}) + 2i - gamma_t(P_n) >= k for the least i. For complete graphs, the load-bearing tool is an edge-count bound (Theorem 9) that limits how many edges a connected graph with a fixed total domination number can have, combined with induction over disconnected components to show no cheaper deletion set exists.

What would settle it

Check the single case n=5, k=2 for paths. The path P_5 has exactly two non-pendant edges and they share a vertex, so deleting both isolates a vertex; the definition of $b_t^{2}$(P_5) is then undefined, whereas the formula for n ≡ 1 (mod 4) gives $b_t^{2}$(P_5) = 2. This one computation settles whether Theorem 3 holds as stated.

Watch

Extended reading notes

Core claim

For a graph G with no isolated vertices, the k-total bondage number b_t^k(G) is the minimum number of edges whose removal leaves no isolated vertices and increases the total domination number by at least k. The paper's exact results are: for paths and cycles, b_t^k(P_n) depends only on n modulo 4 (with b_t^k(C_n) = b_t^k(P_n)+1); for wheels, $b_t^{{k-1}}$(W_n)=k whenever n>=3k and exact formulas cover the maximum possible increases; for complete graphs, b_t^k(K_n) = nk - ($k^{2}$+2k)/2 for even k and nk + n - ($k^{2}$+4k+5)/2 for odd k. The proofs work by showing that the most edge-efficient deletions carve off disjoint single-edge components, then use an edge-count bound for connected graphs to rule out cheaper strategies.

Load-bearing premise

The path and cycle formulas assume that deleting i edges from a path can always be arranged to leave i disjoint single-edge components plus one long path, with total domination number gamma_t(P_{n-2i}) + 2i, and that such a deletion pattern never strands an isolated vertex.

Editorial extensions

If this is right

  • For paths and cycles, once n is large enough relative to k, the k-total bondage number is periodic in n modulo 4 and grows linearly in k, with cycles needing exactly one more deleted edge than paths.
  • For complete graphs, each additional unit of required increase in total domination costs roughly n - k/2 more deleted edges, with a parity-dependent constant in the exact formula.
  • For wheels with n>=3k, deleting k edges raises the total domination number from 2 to k+1, and the maximum possible increase has separate exact formulas for even and odd n.
  • For complete bipartite graphs with b<=2a, exactly b edges must be deleted to raise total domination by 2; for other regimes the paper gives two competing upper bounds.
  • Every integer b >= k/2 occurs as the k-total bondage number of some graph, so the only universal lower bound is the trivial one coming from each deleted edge raising total domination by at most 2.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Beyond the paper: the path and cycle formulas likely need a small-order correction; the case n=5, k=2 suggests the stated domain n>=2k is not sufficient to guarantee that the optimal deletion pattern avoids isolated vertices.
  • Beyond the paper: since complete graphs are the hardest to raise, the complete-graph formula can serve as a worst-case benchmark for network fault tolerance under the transmitter model; one could compare b_t^k of any actual network against nk - O(k^2) to see how much more resilient it is.
  • Beyond the paper: the single-edge-component strategy suggests a general upper bound for arbitrary graphs, namely that graphs containing many edge-disjoint near-pendant structures should have k-total bondage controlled by local vertex degrees; this is testable on random regular graphs.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 3 minor

Summary. The paper introduces the k-total bondage number b_t^k(G), the minimum number of edges whose deletion increases the total domination number γ_t(G) by at least k, under the convention that the resulting graph has no isolated vertices. It proves a general bound on the effect of a single edge deletion, derives exact values for paths, cycles, wheels, and complete graphs, gives bounds for complete bipartite graphs, and constructs graphs with prescribed k-total bondage numbers. The main advertised results are Theorems 3 and 10, which give closed-form formulas for b_t^k of paths/cycles and complete graphs.

Significance. If correct, the exact formulas for paths, cycles, and complete graphs would be a natural and useful extension of total bondage theory to a multi-edge setting. The paper also contains some sound auxiliary material: Theorem 1 is a correct and simple bound, and Theorem 15 provides an existence construction for prescribed k-total bondage numbers. However, the two flagship exact-value theorems are false, with explicit counterexamples already at small parameters, so the paper's central contribution is not established.

major comments (4)
  1. [3.1, Theorem 3] The formula is false in the stated range and may be undefined. For k=2 and n=5, the theorem predicts b_t^2(P_5)=2, but every 2-edge deletion from P_5 either isolates a vertex or leaves the disjoint union P_2 ∪ P_3, whose total domination number is 2+2=4, i.e., only γ_t(P_5)+1=4. Hence no admissible 2-edge deletion raises γ_t by 2, so b_t^2(P_5) is undefined. The proof's use of Corollary 2 assumes that deleting i edges can realize the component decomposition P_{n-2i} ∪ iP_2, but Corollary 2 only compares sums of path total domination numbers; it does not show such a decomposition is attainable from P_n by i edge deletions without isolating vertices.
  2. [3.3, Theorem 10] The odd-k formula is contradicted by n=6, k=3: it gives b_t^3(K_6)=18+6-(9+12+5)/2=11, but after any 11-edge deletion from K_6 the remaining graph has 4 edges on 6 vertices and, being isolate-free, must be P_2 ∪ P_4 or P_3 ∪ P_3, each with γ_t=4 < γ_t(K_6)+3=5. Deleting a perfect matching (12 edges) leaves 3P_2 with γ_t=6, so b_t^3(K_6)=12. The induction in the proof fails because the odd-k construction for k=3 applies Theorem 7 to a remaining K_4 component; Theorem 7 is stated only for n≥5, and indeed b_t^1(K_4)=4 ≠ 2·4−5=3.
  3. [3.2, Theorem 6] The upper-bound construction is incorrect. For k=2 and n=6, the proof removes the two edges v_0v_3 and v_0v_6 from W_6 and claims the total domination number becomes k+1=3. In fact, the set {v_1,v_4} is a TD-set of the resulting graph (v_2 and v_6 are adjacent to v_1; v_3 and v_5 to v_4; v_0 to both), so γ_t remains 2 and no increase by k−1=1 occurs. The lower-bound argument is also not a rigorous proof, since it does not specify how the claimed TD-set is chosen for all possible configurations of fewer than k deleted edges.
  4. [3.3, proof of Theorem 7] The claimed complete proof of Theorem 7 contains an unsupported step in Case 2: the assertion that a' and b' can always be chosen adjacent is justified by a displayed inequality whose positivity is not established, and the reduction to this configuration is not argued. Because Theorem 7 is used as the k=1 base case for the induction in Theorem 10, this gap independently undermines the proof of the main theorem, even apart from the counterexample in the preceding comment.
minor comments (3)
  1. [3.2, Theorem 5] In the sentence 'Since n+1 is even, not all vertices can be in the total dominating set', the parity statement is backwards: for even n, n+1 is odd. Please correct the wording.
  2. [3.1, Corollary 1] The notation P_a + P_b for the disjoint union is used without definition; please define it when first used.
  3. [3.4, after Theorem 13] The sentence 'Note that in some cases we would start with one strategy and then change as k increases' is vague; the comparison of the two bounds should be stated precisely with the relevant inequalities.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: exact values are derived from external theorems and fresh base constructions; the possible counterexamples are correctness concerns, not circular reductions.

full rationale

The derivation chain is self-contained in the circularity sense. The k-total bondage number is a fresh definition, not a renamed known result. The path and cycle values in Theorem 3 follow from Lemma 1, Proposition 1 (Henning–Yeo), and Corollary 2, which is proved from those results rather than assumed. The smallest-i inequality in Theorem 3 is a direct computation from Proposition 1, not a fitted or renamed version of the target value. Theorem 7 is quoted from Kulli–Patwari but immediately reproved with a minimal-counterexample argument, so no load-bearing self-citation is involved. Theorem 9 is an external edge-count bound of Sanchis, and Lemma 2 is proved algebraically. Theorem 10 uses strong induction on k with strictly smaller parameters plus the external bound; applying the induction hypothesis to smaller k and to complete graphs on smaller order is legitimate, not circular. No parameter is fitted to data and then renamed as a prediction, and no central premise is justified solely by a self-citation. The alleged failures for P5 with k=2 and K6 with k=3 are correctness risks in the stated formulas, not examples of a prediction reducing to its input by construction; a false theorem is not the same as a circular derivation. Therefore no circular steps are identified.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper depends on standard graph-theory background and several cited theorems, not on fitted parameters or new entities. The main hidden assumption is that deletions producing the extremal component structure are always legal, which fails for small paths and wheels.

assumptions (4)
  • domain assumption Graphs are finite, simple, undirected and all graphs considered after edge deletions have no isolated vertices.
    Stated in Section 1; this makes the total domination number well-defined and is critical for whether b_t^k exists.
  • standard math Total domination number of paths and cycles is given by Proposition 1 of Henning and Yeo.
    Used in Theorem 3 to translate edge-deletion counts into domination-number increases.
  • standard math Sanchis' edge bound for connected graphs with gamma_t >= 5.
    Used in Theorem 10 to rule out connected graphs with too few edges and high gamma_t.
  • standard math Total bondage results for wheels and complete bipartite graphs from Kulli and Patwari.
    Serves as k=1 base cases and context for Theorems 6, 12, 13, and 14.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The $k$-Total Bondage Number of a Graph." pith.science (2026). https://pith.science/paper/ZSBHNSRB

@misc{pith2026250607000,
  author       = {Pith},
  title        = {Pith review of: The $k$-Total Bondage Number of a Graph},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZSBHNSRB}},
  note         = {Machine review of arXiv:2506.07000}
}
abstract

Let $G=(V,E)$ be a connected, finite undirected graph. A set $S \subseteq V$ is said to be a total dominating set of $G$ if every vertex in $V$ is adjacent to some vertex in $S$. The total domination number, $\gamma_{t}(G)$, is the minimum cardinality of a total dominating set in $G$. We define the $k$-total bondage of $G$ to be the minimum number of edges to remove from $G$ so that the resulting graph has a total domination number at least $k$ more than $\gamma_{t}(G)$. We establish general properties of $k$-total bondage and find exact values for certain graph classes including paths, cycles, wheels, complete and complete bipartite graphs.

Figures

Figures reproduced from arXiv: 2506.07000 by the authors.

Figure 1
Figure 1. A minimal TD-set which is not a minimum TD-set. [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Comparison of total bondage numbers, showing deletions need not be successive [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Wheels with the maximum increase to their total domination number [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figures from the paper (10 more)
Figure 4
Figure 4. Figure 4: Examples with n = 8 showing that the removal of a minimum TD-set does not imply existence of two vertices of degree 2 Case 1: If deg(x) = n − 1 or n − 2 then the result follows from a similar argument as the base case. Case 2: Suppose that deg(x) = n − 3. Let G′ = G \ …
Figure 5
Figure 5. Figure 5: G = Kn \ S with subgraph G′′ We categorize V (G′′) as follows: Let X2 ⊆ V (G′′) be the set of vertices in G′′ which are adjacent to a ′ and b ′ , i.e. X2 = N(a ′ ) ∩ N(b ′ ) ∩ V (G′′). Let X1 ⊆ V (G′′) be the set of vertices in G′′ which are adjacent to exactly one of …
Figure 6
Figure 6. Figure 6: G′′: For each vertex in X1, only one of the dotted lines is an edge |X2| + |X1| + |X0| = n − 5 and G′′ has n − 5 fewer edges than Kn−3, so |X0| = 0. Then {a ′ , b′} is a TD-set of G. Case 3: Suppose there exists no x ∈ V (G) such that deg(x) ≥ n − 3. Recall that D(G) =…
Figure 7
Figure 7. Figure 7: Kulli and Patwari’s method: b 1 t (K3,6) 16 [PITH_FULL_IMAGE:figures/full_fig_p016_7.png]
Figure 8
Figure 8. Figure 8: b 2 t (K3,6) = 6 We have found cases that show Theorem 12 is not a strict bound, so we now give another method that in those cases improves on the above strategy. Theorem 13. For a complete bipartite graph with ⌈ k 2 ⌉ + 1 ≤ a ≤ b, b k t (Ka,b) ≤  k 2  a + b −  k 2…
Figure 9
Figure 9. Figure 9: b 2 t (K4,5) = 7 a stricter bound for even k when a < b − k 2 − 1. For odd k we have a similar result, that Theorem 12 gives a stricter bound when a < b k+1 k−1  − k−1 2 . Likewise, when the sign is flipped Theorem 13 gives a stricter bound. In the case that the total…
Figure 10
Figure 10. Figure 10: b 2 t (K3,5) = 5 Theorem 15. For any positive integers k and b ≥ k 2 , there exists a graph Gk b where b k t (Gk b ) = b. Proof. By Theorem 1, we can increase γt(G) by at most two for each edge we remove, so b ≥ k 2 . Given two graphs G and H with g ∈ V (G) and h ∈ V …
Figure 11
Figure 11. Figure 11: Case 1 when k odd and r = 1. For example k = 7 and b = 4 x a (a) G7 5 = (T 3 5 )x ⊕ (K4 \ {e})a′ x a (b) b 7 t (G7 5 ) = 5 [PITH_FULL_IMAGE:figures/full_fig_p020_11.png]
Figure 12
Figure 12. Figure 12: Case 1 when k odd and r = 2. For example k = 7 and b = 5 20 [PITH_FULL_IMAGE:figures/full_fig_p020_12.png]
Figure 13
Figure 13. Figure 13: Case 1 when k odd and r = 5. For example k = 7 and b = 8 Corollary 4. For any k and b, there exists a graph G where b k+1 t (G) = b k t (G) + b. Proof. The result follows from Theorem 15. Let m = ⌊ k 2 ⌋. When k is even, consider G = T m b+1 and when k is odd, conside…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

17 extracted references · 13 canonical work pages

  1. [1]

    Berge, Théorie des graphes et ses applications, Vol

    C. Berge, Théorie des graphes et ses applications, Vol. II of Collection Universitaire de Mathématiques, Dunod, Paris, 1958

    work page 1958

  2. [2]

    Ore, Theory of graphs, Vol

    O. Ore, Theory of graphs, Vol. Vol. XXXVIII of American Mathemat- ical Society Colloquium Publications, American Mathematical Society, Providence, RI, 1962

    work page 1962

  3. [3]

    Cockayne, S

    E. Cockayne, S. Hedetniemi, Optimal domination in graphs, IEEE Transactions Circuits and Systems CAS-2 (11) (1975) 855–857.doi: 10.1109/TCS.1975.1083994. URLhttps://doi.org/10.1109/TCS.1975.1083994

    work page arXiv 1975

  4. [4]

    Cockayne, S

    E. Cockayne, S. Hedetniemi, Disjoint independent dominating sets in graphs, Discrete Mathematics 15 (3) (1976) 213–222.doi:10.1016/ 0012-365X(76)90026-1. URLhttps://doi.org/10.1016/0012-365X(76)90026-1

    work page doi:10.1016/0012-365x(76)90026-1 1976

  5. [5]

    Cockayne, S

    E. Cockayne, S. Hedetniemi, Towards a theory of domination in graphs, Networks 7 (3) (1977) 247–261.doi:10.1002/net.3230070305. URLhttps://doi.org/10.1002/net.3230070305 21

    doi:10.1002/net.3230070305 1977

  6. [6]

    Cockayne, Domination of undirected graphs—a survey, Theory and applications of graphs (Proc

    E. Cockayne, Domination of undirected graphs—a survey, Theory and applications of graphs (Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976) Vol. 642 (1978) 141–147

    work page 1978

  7. [7]

    D. Du, P. Wan, Connected dominating set: theory and applications, Vol. 77 of Springer Optimization and Its Applications, Springer, New York, 2013.doi:10.1007/978-1-4614-5242-3. URLhttps://doi.org/10.1007/978-1-4614-5242-3

    work page doi:10.1007/978-1-4614-5242-3 2013

  8. [8]

    Haynes, S

    T. Haynes, S. Hedetniemi, P. J. Slater, Fundamentals of Domination in Graphs, 1st Edition, CRC Press, 1998.doi:10.1201/9781482246582

    doi:10.1201/9781482246582 1998

Show all 17 references
  1. [9]

    L. L. Kelleher, Domination in graphs and its application to social network theory, ProQuest LLC, Ann Arbor, MI, 1985, thesis (Ph.D.)– Northeastern University. URLhttp://gateway.proquest.com/openurl?url_ver=Z39. 88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation& res_dat=xri...

    1985

  2. [10]

    E. J. Cockayne, R. M. Dawes, S. T. Hedetniemi, Total domina- tion in graphs, Networks 10 (3) (1980) 211–219.doi:10.1002/net. 3230100304. URLhttps://doi.org/10.1002/net.3230100304

    1980 doi

  3. [11]

    M. A. Henning, A. Yeo, Total domination in graphs, Springer Mono- graphs in Mathematics, Springer, New York, 2013.doi:10.1007/ 978-1-4614-6525-6. URLhttps://doi.org/10.1007/978-1-4614-6525-6

    2013 doi

  4. [12]

    Bauer, F

    D. Bauer, F. Harary, J. Nieminen, C. Suffel, Domination alteration sets in graphs, Discrete Mathematics 47 (1983) 153–161.doi:10.1016/ 0012-365X(83)90085-7

    1983

  5. [13]

    URLhttps://doi.org/10.1016/0012-365X(90)90348-L

    J.F.Fink, M.S.Jacobson, L.F.Kinch, J.Roberts, Thebondagenumber of a graph, Discrete Mathematics 86 (1-3) (1990) 47–57.doi:10.1016/ 0012-365X(90)90348-L. URLhttps://doi.org/10.1016/0012-365X(90)90348-L

    1990 doi

  6. [14]

    J. M. Xu, On bondage numbers of graphs: A survey with some comments, International Journal of Combinatorics 2013 (1) (2013) 22 595210.doi:https://doi.org/10.1155/2013/595210. URLhttps://onlinelibrary.wiley.com/doi/abs/10.1155/2013/ 595210

    2013 doi

  7. [15]

    Anaya, A

    R. Anaya, A. Belmonte, N. Shank, E. Sinani, B. Walker, Generalized bondage number: Thek-synchronous bondage number of a graph, Ball State Undergraduate Mathematics Exchange (to appear, 2025). URLhttps://arxiv.org/abs/2208.07484

    2025 arXiv

  8. [16]

    V. R. Kulli, D. K. Patwari, The total bondage num- ber of a graph, Advances in graph theory (1991) 227–235doi:https://www.researchgate.net/profile/ V-Kulli/publication/293504205_The_total_bondage_ number_of_a_graph/links/56fe8b5a08ae650a64f72094/ The-total-bondage-number-of-a-...

    1991

  9. [17]

    L. A. Sanchis, Relating the size of a connected graph to its total and restricted domination numbers, Discrete Mathematics 283 (1-3) (2004) 205–216.doi:https://doi.org/10.1016/j.disc.2003.11.011. 23

    2004 doi

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.