Combinatorics · arXiv:2611.16338 v1 · submitted 12 Nov 2026 · 23 references
Total edge irregularity strength of cubic graphs
The paper says
“We show that every finite simple cubic graph on n vertices has total edge irregularity strength n/2 + 1, confirming the Ivančo-Jendrol' conjecture for cubic graphs.”
more of the abstract
The key step is to algorithmically construct a {1,n/2 + 1}-vertex labeling such that half of the vertices are labeled 1 and the average degree of the subgraph induced by them is close enough to two. We extend such a labeling to a total edge irregular (n/2 + 1)-labeling, possibly after a local adjustment to a single vertex.
from the abstract
Pith says
Machine review · deepseek-v4-flash · 13 Nov 2026 · what was read was not recorded · not checked by a person
It can be wrong. Challenge this review or reply to it.
The passes disagreed. Reader: holds up. Skeptic: holds up only with conditions. Referee: major revision.
The paper claims to prove the Ivančo-Jendrol' conjecture for all cubic graphs via a constructive labeling algorithm. The proof has a gap in the swap step that the authors do not address. This line is wrong
3 major objections · 5 minor
How often objections from reviews like this one are right: not yet measured
Not checked: figures, code, what the 23 references say.
The paper says, at Section 3, after equation [b56]
The review did not quote this passage.
Pith says: Objection 1 of 3 · major
The claim that 'we can find a vertex u in U (resp. v in V(G)\U) all three of whose neighbors are in U (resp. V(G)\U)' is not justified. The average degree dU > 2 only guarantees existence of a vertex with degree at least 3 in G[U], but not that all three neighbors are in U.
more of objection 1
In a cubic graph, a vertex in U could have degree 3 in G[U] (i.e., all three neighbors in U) or degree 2 in G[U] (two neighbors in U, one outside) or degree 1 or 0. The average being >2 forces at least one vertex with degree 3 in G[U], but the symmetric condition for V(G)\U is not guaranteed by the same average degree argument because the average degree in the complement is also dU > 2, so similarly there exists a vertex in V(G)\U with all three neighbors in V(G)\U. However, the swap step also requires that u and v are not adjacent, which is not argued. Moreover, the algorithm requires that such a pair exists simultaneously; the existence of a vertex u in U with all neighbors in U and a vertex v in V(G)\U with all neighbors in V(G)\U does not guarantee they are non-adjacent. If they are adjacent, swapping would change the count differently. The paper does not address this. This is a gap in the constructive proof.
The paper says, at Section 3, initial construction of U
The review did not quote this passage.
Pith says: Objection 2 of 3 · major
The construction of U uses a subtree S of a spanning tree T of component G_{k+1} with exactly n/2 - ρ vertices. The paper states 'pick any subtree S of T having n/2 - ρ vertices.' It is a known fact that every tree on N vertices contains a subtree of every order from 1 to N, but this is not stated.
more of objection 2
While this is a standard fact, the paper should at least mention it or provide a brief justification. However, this is a minor issue; the major gap is the swap step.
The paper says, at Section 3, final adjustment case
The review did not quote this passage.
Pith says: Objection 3 of 3 · major
In the exceptional case (a,b,c) = (s-2, s+1, s-2), the paper changes the label of a vertex u from 1 to 2. It claims that 'we can find a vertex u in U that has at most one neighbor in U' because dU < 2.
more of objection 3
This is correct: average degree < 2 implies existence of a vertex with degree at most 1 in G[U]. However, the subsequent edge label assignments for the two subcases (0 or 1 neighbor in U) need to be checked for consistency with the admissibility lemma or directly verified. The tables provided seem plausible, but the paper does not verify that all edge labels are in [1,s] and that the weight intervals are disjoint. For the first subcase (0 neighbors), the table assigns edge labels for E2s as [3,s], but the number of edges in E2s is s-2, so the labels [3,s] have size s-2? Actually [3,s] has s-2 elements (3,4,...,s). That's fine. But the weight intervals: E2s weights are [2s+3, 3s]? Let's compute: if edge label is l, weight = 2s + l? Actually for E2s, both endpoints have label s, so weight = s + l + s = 2s + l. So if l ranges from 3 to s, weight ranges from 2s+3 to 3s. That's disjoint from previous interval [2s, 2s+2]? The previous interval is from Es+2: weight = 1 + l + s? Wait, need to check carefully. The paper's table for the first subcase: Es+2 edge labels [s-2, s], weights [2s, 2s+2]. For l=s-2, weight = 1 + (s-2) + s = 2s-1? Actually the vertex labels: u is changed to 2, so the edge in Es+2 has endpoints: one with label 2, one with label s? Actually Es+2 is defined as edges where sum of endpoint labels = s+2. Since u has label 2, its neighbor in U? Wait, the subcase is u has 0 neighbors in U, so all three neighbors are in V(G)\U with label s. So edges incident to u are between label 2 and label s, sum = s+2, so they belong to Es+2. The other edges in Es+2? Possibly none. The table says Es+2 edge labels [s-2, s], weights [2s, 2s+2]. But if edge label is s-2, weight = 2 + (s-2) + s = 2s? Actually 2 + (s-2) + s = 2s. If edge label is s, weight = 2 + s + s = 2s+2. So that matches. Then E2s weights: edge label l, weight = s + l + s = 2s + l. For l from 3 to s, weight from 2s+3 to 3s. So disjoint from [2s,2s+2]. Good. However, the paper does not verify that the edge labels for E2s are within [1,s] and that the number of labels matches the count. The table says E2s edge labels [3,s], which has size s-2, matching c=s-2. But is the label 1 used?
5 minor objections
The paper says, at Section 3, after [b55]
Pith says: minor objection 1 of 5
The inequality a >= n/2 - 1 = s-2 is derived assuming S is a tree. But S is a subtree of a spanning tree, so it is a tree. The number of edges in S is (n/2 - ρ) - 1.
more of objection 1
The sum includes edges from components G_i for i=1..k, each cubic, so |E(G_i)| = 3n_i/2. The sum of those is 3ρ/2. So a >= 3ρ/2 + (n/2 - ρ - 1) = n/2 + ρ/2 - 1. Since ρ < n/2, this is at least n/2 - 1? Actually n/2 + ρ/2 - 1 >= n/2 - 1 because ρ/2 >= 0. So a >= s-2. That's correct. But note that a is the number of edges with both endpoints in U, which includes edges inside each G_i and inside S, but also possibly edges between components? Since components are disconnected, there are no edges between different G_i. Also, S is a subtree of G_{k+1}, so edges inside S are counted. However, there might be edges in G_{k+1} that are not in S but have both endpoints in S? Since S is a subtree, it includes all vertices of S but only some edges; there could be additional edges in G_{k+1} between vertices of S that are not in the spanning tree T. The paper uses |E(S)| as the number of edges in the subtree S, but the actual number of edges in G[U] could be larger because G_{k+1} may have extra edges not in T. The paper's lower bound a >= ... uses |E(S)|, which is a lower bound on the number of edges inside U from component G_{k+1}. However, the paper says 'a ≥ ... |E(S)| = ...' which is valid because a counts all edges inside U, which includes at least the edges of S. So the inequality is correct. But the paper should clarify that S is a subtree, not necessarily an induced subgraph, and that the edges of S are a subset of edges of G[U]. This is fine.
The paper says, at Section 2, Lemma 2.1
Pith says: minor objection 2 of 5
The lemma states an if-and-only-if characterization. The necessity is clear. The sufficiency construction assigns edge labels in intervals. The paper should verify that the intervals for edge labels are within [1,s] and that the weight intervals are disjoint. The proof does this, but there is a minor typo: in the definition of β, it says β = max{1, α+b+1-s}.
more of objection 2
Then the edge labels for Es+1 are from [α, α+b-1]. The largest label is α+b-1. The paper claims α+b-1 = max{b, a+b+1-s} ≤ s. But α = max{1, a+2-s}. So α+b-1 = max{b, a+b+1-s}? Let's check: if α = 1, then α+b-1 = b. If α = a+2-s, then α+b-1 = a+b+1-s. So yes. The condition a+b ≤ 2s-1 ensures a+b+1-s ≤ s. And b ≤ s from a,b,c ≤ s. So α+b-1 ≤ s. Similarly for β. This is correct.
show 3 more
The paper says, at Section 3, after [b60]
Pith says: minor objection 3 of 5
The paper states that the final distribution (a,b,c) is one of (s, s-3, s), (s-1, s-1, s-1), (s-2, s+1, s-2). This follows from a ∈ {s-2, s-1, s} and the equations 3|U| = 2a+b and 3|V(G)\U| = 2c+b, with |U| = n/2, |V(G)\U| = n/2, and a=c.
more of objection 3
But the paper should verify that b is determined uniquely by a. From 3n/2 = 2a+b, so b = 3n/2 - 2a = 3s-3 - 2a. For a=s, b=3s-3-2s = s-3. For a=s-1, b=3s-3-2(s-1)=s-1. For a=s-2, b=3s-3-2(s-2)=s+1. So indeed. The paper should state this explicitly.
The paper says, at Section 3, final adjustment
Pith says: minor objection 4 of 5
In the exceptional case, the paper changes the label of u from 1 to 2. This changes the vertex labeling to use three labels: 1, 2, s. The admissibility lemma only covers vertex labelings using {1,s}. So the extension to a total edge irregular labeling is done directly via tables, not via Lemma 2.1. The paper should state this explicitly. It does, but the transition could be clearer.
The paper says, at General
Pith says: minor objection 5 of 5
The paper uses the notation s = n/2 + 1. For n even, s is integer. For n odd? Cubic graphs have even number of vertices because sum of degrees is 3n, which must be even, so n is even. So s is integer. Good.
What would settle it
Construct a cubic graph on n=6 vertices (e.g., the triangular prism) and run the described algorithm: choose initial U as described, then attempt the swap step. Check whether at each iteration with a > s there exists a vertex u in U with all three neighbors in U and a vertex v in V(G)\U with all three neighbors outside U, with u and v nonadjacent. If the algorithm fails to find such a pair for some cubic graph, the proof is incomplete.
from the skeptic's reading
How the review went
4 readings by deepseek-v4-flash · 13 Nov 2026
- Reader holds up
- Skeptic disagrees: says it holds up only with conditions The swap step assumes existence of a vertex u in U with all three neighbors in U when dU > 2, but the argument only guarantees average degree > 2, not that any vertex has degree 3 inside U.
- Editor wrote the verdict above
- Referee major revision: 3 major objections, 5 minor
Not run on this paper: the simulated authors' defence.
Pith did not check this review's objections against the paper.
The review in full
The review in brief, machine-written
The paper claims to prove the Ivančo-Jendrol' conjecture for all cubic graphs via a constructive labeling algorithm. The proof has a gap in the swap step that the authors do not address.
The strongest objection
In the iterative reduction step (after [b56]), the authors write: 'It follows that we can find a vertex u ∈ U (resp. v ∈ V(G)\U) all three of whose neighbors are in U (resp. V(G)\U).' This is a non-sequitur. The average degree of the induced subgraph G[U] is dU = 2a/|U| = 2a/(s-1). When a > s, we have dU > 2s/(s-1) > 2, but average degree > 2 does not imply any vertex has degree 3 inside U. For a cubic graph, vertices in U can have 0,1,2,3 neighbors in U. The average being >2 only forces that there is at least one vertex with degree at least 3 (i.e., degree 3) in G[U], but the swap step requires a vertex u ∈ U with all three neighbors in U *and* a vertex v ∈ V(G)\U with all three neighbors outside U. The latter condition is symmetric but also not guaranteed by average degree >2 in the complement. Moreover, the swap step also requires that u and v are not adjacent, which is not argued. If such a pair does not exist, the reduction cannot proceed and the algorithm may stall before reaching a ≤ s. This is a gap in the constructive proof.
The reader's weakest_assumption focused on the existence of a subtree of prescribed order, which is standard and true. The more serious concern is the swap step's existence claim, which is not justified and is central to the reduction. The paper does not provide a proof that such vertices u and v always exist when a > s. Without this, the algorithm may not terminate, and the main theorem is not established. The concern is load-bearing because the entire reduction from a > s to a ≤ s depends on it. The concrete test on a small cubic graph would reveal whether the claim holds in all cases or if a counterexample exists. I recommend CONDITIONAL acceptance pending a justification or modification of the swap step.
The referee's report
If correct, this would be a significant result, settling the conjecture for all cubic graphs, complementing Pfender's large-graph result with an explicit construction for all orders. The paper provides a deterministic algorithm, which is valuable.
Pith's reading of the paper (a machine's summary, not the authors')
Graph labelers ask how few numbers you can write on vertices and edges of a network so that no two edges give the same sum. For a graph where every vertex has three neighbors, the number of edges is one and a half times the number of vertices, so a counting argument forces at least n/2+1 different labels. This paper proves that n/2+1 labels are always enough, settling the conjecture for cubic graphs.
The proof is constructive. Start by putting the small label on half the vertices and the large label on the other half. Count the three kinds of edges: small-small, small-large, large-large. If there are too many small-large edges, the proof shows one can swap a small vertex with a large vertex in a way that reduces that count by exactly three, without changing the size of either half. Repeating this eventually reaches a distribution that can be extended to a full labeling.
One exceptional distribution remains. In that case the authors change a single vertex from the small label to the middle label 2 and fill in the edge labels with two explicit tables. They check that every edge label stays in the allowed range and every edge weight lands in a separate interval, so all sums are distinct. The argument covers disconnected graphs as well, and it handles the smallest cubic graph K4 explicitly.
Core claim. Theorem A states that every finite simple cubic graph G on n vertices satisfies tes(G) = n/2+1. If the proof is correct, the Ivančo-Jendrol' conjecture is true for every cubic graph, connected or not, and the lower bound from (1) is always attained by an explicit total edge irregular labeling rather than only by a probabilistic existence argument.
The premise it rests on. The initial construction of U requires choosing, inside the spanning tree T of component G_{k+1}, a subtree S with exactly n/2−ρ vertices. The paper does not state the supporting fact that every tree on N vertices contains a connected subtree of every order from 1 to N, though this fact is standard and true. If it failed, the initial set U might not have both size n/2 and at least s−2 edges inside it, and the whole reduction would not get started. This enters in Section 3 at the sentence 'pick any subtree S of T having n/2−ρ vertices.'
Check this review
Pith stored no record of this review's passes and took no fingerprint of it. Reviews made by code from 13 Nov 2026 on carry both.
How often reviews like this one are right
Reviews like this one: written by deepseek-v4-flash, where what was read was not recorded.
How often objections from reviews like this one are right: not yet measured
Reviews by people
This review was written by a machine. No person has reviewed this paper on Pith yet. A scientist listed on Pith can review it for a fee, and their review is published here whatever it concludes.
The paper
Abstract
We show that every finite simple cubic graph on n vertices has total edge irregularity strength n/2 + 1, confirming the Ivančo-Jendrol' conjecture for cubic graphs. The key step is to algorithmically construct a {1,n/2 + 1}-vertex labeling such that half of the vertices are labeled 1 and the average degree of the subgraph induced by them is close enough to two. We extend such a labeling to a total edge irregular (n/2 + 1)-labeling, possibly after a local adjustment to a single vertex.
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. No sentence in this record was written by a model.
abstract compiled · 2026-11-13
The authors' main claim, as the classifier picked it out 1.00
“We show that every finite simple cubic graph on $n$ vertices has total edge irregularity strength $n/2+1$, confirming the Ivan\v{c}o-Jendrol' conjecture for cubic graphs.”
How the main claim is stated: asserted 1.00
What the abstract itself states, as probabilities: claims first 0.07 · states limitation 0.27 · human participants 0.02 · controlled comparison 0.02 · randomized assignment 0.01 · states quantitative result 0.98 · compares with prior results 0.39 · mentions code or data availability 0.02
The abstract, sentence by sentence
This table labels the abstract only (arXiv listing abstract v1). The number is the probability the classifier gave the label.
| Sentence | Role | The authors' own work | States the main conclusion | Strength |
|---|---|---|---|---|
| We show that every finite simple cubic graph on $n$ vertices has total edge irregularity strength $n/2+1$, confirming the Ivan\v{c}o-Jendrol' conjecture for cubic graphs. | result 0.95 | 0.96 | 0.97 | asserted 1.00 |
| The key step is to algorithmically construct a $\{1,n/2+1\}$-vertex labeling such that half of the vertices are labeled $1$ and the average degree of the subgraph induced by them is close enough to two. | method 0.99 | 0.91 | 0.04 | asserted 0.99 |
| We extend such a labeling to a total edge irregular $(n/2+1)$-labeling, possibly after a local adjustment to a single vertex. | method 0.95 | 0.94 | 0.06 | hedged possibility 0.68 |
What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00
What was examined, and what was not
Sources read
- arXiv listing abstract v1
Not examined
- full text
- figures and tables
- references and citing sentences
- relations to other papers
Levels run
- P abstract
Not run
- S sections
- T body sentences
- C citations
- R cross-paper relations
How the labels were made
Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-11-13: 1 request, 3,049 input tokens.
Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. This record as JSON
References (23)
- [1] A. Ahmad and M. Bača, “Total edge irregularity strength of a categorical product of two paths,” Ars Combinatoria114(2014), 203–212 on Pith
- [2] A. Ahmad, M. Bača, Y. Bashir, and M. K. Siddiqui, “Total edge irregularity strength of strong product of two paths,”Ars Combinatoria106(2012), 449–459. https://combinatorialpress. com/ars-articles/volume-106-ars-articles/ on Pith
- [3] A. Ahmad, M. Bača, and M. K. Siddiqui, “On edge irregular total labeling of categorical product of two cycles,”Theory of Computing Systems54(2014), 1–12. https://doi.org/10.1007/ s00224-013-9470-3 on Pith
- [4] A. Ahmad, M. Bača, and M. K. Siddiqui, “Irregular total labeling of disjoint union of prisms and cycles,”Australasian Journal of Combinatorics59(2014), 98–106. https://ajc.maths.uq.edu. au/pdf/59/ajc_v59_p098.pdf on Pith
- [5] M. Bača, S. Jendrol’, M. Miller, and J. Ryan, “On irregular total labellings,”Discrete Mathematics 307(2007), 1378–1388.https://doi.org/10.1016/j.disc.2005.11.075 on Pithdoi:10.1016/j.disc.2005.11.075
- [6] M. Bača, M. Lascsáková, and M. K. Siddiqui, “Total edge irregularity strength of toroidal fullerene,”Mathematics in Computer Science7(2013), 487–492. https://doi.org/10.1007/ s11786-014-0172-2 on Pith
- [7] M. Bača and M. K. Siddiqui, “Total edge irregularity strength of generalized prism,”Applied Mathematics and Computation235(2014), 168–173. https://doi.org/10.1016/j.amc.2014. 03.001 on Pithdoi:10.1016/j.amc.2014
- [8] A. Barra and M. Afifurrahman, “The total vertex irregularity strength for cubic graphs with a perfect matching,”Discrete Mathematics348(5) (2025), Article 114402. https://doi.org/10. 1016/j.disc.2025.114402. 5 on Pith
- [9] S. Brandt, J. Miškuf, and D. Rautenbach, “On a conjecture about edge irregular total labelings,” Journal of Graph Theory57(2008), 333–343.https://doi.org/10.1002/jgt.20287 on Pithdoi:10.1002/jgt.20287
- [10] S. Brandt, J. Miškuf, and D. Rautenbach, “Edge irregular total labellings for graphs of linear size,”Discrete Mathematics309(2009), 3786–3792. https://doi.org/10.1016/j.disc.2008. 10.009 on Pithdoi:10.1016/j.disc.2008
- [11] G. Chartrand, M. S. Jacobson, J. Lehel, O. R. Oellermann, S. Ruiz, and F. Saba,Irregular networks, Congressus Numerantium64(1988), 197–210 on Pith
- [12] J. A. Gallian, “Graph labeling,”The Electronic Journal of Combinatorics, Dynamic Survey DS6 (first published 1998; updated October 30, 2025).https://doi.org/10.37236/27 on Pithdoi:10.37236/27
- [13] K. M. M. Haque, “Irregular total labellings of generalized Petersen graphs,”Theory of Computing Systems50(2012), 537–544.https://doi.org/10.1007/s00224-011-9350-7 on Pithdoi:10.1007/s00224-011-9350-7
- [14] J. Ivančo and S. Jendrol’, “Total edge irregularity strength of trees,”Discussiones Mathematicae Graph Theory26(2006), 449–456.https://doi.org/10.7151/dmgt.1337 on Pithdoi:10.7151/dmgt.1337
- [15] S. Jendrol’, J. Miškuf, and R. Soták, “Total edge irregularity strength of complete graphs and complete bipartite graphs,”Discrete Mathematics310(2010), 400–407. https://doi.org/10. 1016/j.disc.2009.03.006 on Pith
- [16] P. Jeyanthi and A. Sudha, “Total edge irregularity strength of wheel related graphs,”Journal of Graph Labeling2(1) (2016), 45–57 on Pith
- [17] F. Pfender, “Total edge irregularity strength of large graphs,”Discrete Mathematics312(2012), 229–237.https://doi.org/10.1016/j.disc.2011.08.027 on Pithdoi:10.1016/j.disc.2011.08.027
- [18] A. S. Saranya and K. R. Santhosh Kumar, “On the total edge irregularity strength of certain classes of cycle related graphs,”Proyecciones43(1) (2024), 53–67.https://doi.org/10.22199/ issn.0717-6279-5728 on Pith
- [19] A. Shabbir, M. F. Nadeem, A. Ovais, F. Ashraf, and S. Nasir, “Total irregularity strengths of an arbitrary disjoint union of (3,6)-fullerenes,”Combinatorial Chemistry & High Throughput Screening25(2022), 500–509.https://doi.org/10.2174/1386207323666201209094514 on Pithdoi:10.2174/1386207323666201209094514
- [20] A. Shabbir, M. Bača, and A. Semaničová-Feňovčíková, “Total irregularity strengths of a disjoint union of (4,6)-fullerene graphs,”Polycyclic Aromatic Compounds43(4) (2023), 3651–3669. https://doi.org/10.1080/10406638.2022.2077392 on Pithdoi:10.1080/10406638.2022.2077392
show 3 more
- [21] Y. Susanti, S. Wahyuni, A. Sutjijana, S. Sutopo, and I. Ernanto, “Generalized arithmetic staircase graphs and their total edge irregularity strengths,”Symmetry14(2022), 1853.https: //doi.org/10.3390/sym14091853 on Pithdoi:10.3390/sym14091853
- [22] R. W. N. Wijaya, J. Ryan, and T. Kalinowski, “Total edge irregularity strength of the Cartesian product of bipartite graphs and paths,”Journal of the Indonesian Mathematical Society29(2) (2023), 156–165.https://doi.org/10.22342/jims.29.2.1321.156-165 on Pithdoi:10.22342/jims.29.2.1321.156-165
- [23] E. Wulandari and Y. Susanti, “On total edge irregularity strength of arithmetic ladder graphs,” AIMS Mathematics11(4) (2026), 10175–10190.https://doi.org/10.3934/math.2026420. 6 on Pithdoi:10.3934/math.2026420
Challenges and discussion
Disagree with the review, or know something it missed? Leave a comment, or challenge this review formally: a challenge becomes a permanent entry in this paper's record, and its decision is published here.
Come back by email
A short list of the week's newly reviewed papers. Nothing is sent until you confirm from your inbox, and every email has a link that stops it. No account.
No comments yet.
Sign in to comment