{"id":"6ac4c23f-a06c-45f7-97f6-0e3eadeb1b4d","arxiv_id":"1908.06072","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every connected graph G with |G| >= 9 and Delta(G) >= |G| - 5 has an antimagic orientation.","lead":"This paper proves that every connected graph with at least nine vertices and a vertex connected to all but at most four others has an antimagic orientation, meaning edges can be directed and numbered so every vertex's net sum is distinct. It is a step toward a 2010 conjecture that all connected graphs have such an orientation.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1.2(ii) depends on an exhaustive figure-based case analysis of H0 that the text does not make checkable; a missing or mislabeled H0 case would break the proof.","rationale":"The reader's weakest assumption identifies the same load-bearing concern: the proof of Theorem 1.2(ii) rests on an exhaustive case analysis presented only in Figures 1 and 2. I checked the surrounding argument in good faith. The reductions that restrict to 1 ≤ Δ(G[Y]) ≤ t−3 via Lemma 2.2 and Theorem 2.3 are sound: if G[Y] is independent, Lemma 2.2 applies; if Δ(G[Y]) ≥ t−2, a vertex in Y is universal in G[Y], so together with x it dominates the graph and Theorem 2.3 applies. The subsequent label assignment is also internally consistent: the ordering y1 ≺ ··· ≺ y t−1 and the sequential choice of labels make the sums s(D1,τ1)(y i) strictly decreasing, the sort of N(x) plus the strictly increasing a i make the sums s(D,τ)(v i) strictly increasing, and the final inequality s(x) < s(y t−1) follows from the displayed estimates provided the figure-dependent facts hold. The estimates themselves, however, are not justified in the text and depend on details of D0 and τ0 that are absent here. This is an addressable but real gap; the verdict should remain CONDITIONAL, as the reader already set it. I found no inconsistency beyond this and no reason to move to ACCEPT or REJECT.","tokens_in":9766,"tokens_out":20512,"duration_ms":198962,"concrete_test":"Obtain the actual figures and independently enumerate all unlabeled graphs H0 arising in the proof: take t ∈ {4, 5}, Y of size t−1 with 1 ≤ Δ(G[Y]) ≤ t−3, choose the r components of G[Y], and attach r external edges from z i ∈ N(x) to each component (z i may coincide), so H0 has vertex set Y ∪ {z i} and edge set E(G[Y]) ∪ {e i}. For every such H0, brute-force search over all orientations and injective labelings with labels from {1,...,6} (plus 10 when H0 = P5 and m ≥ 10) to check existence of a pair satisfying −4 ≤ s(D0,τ0)(y i) ≤ 0 and 0 < |s(D0,τ0)(y i) − s(D0,τ0)(y j)| ≤ 4, and compare the found pairs with Figure 2. Separately verify the Figure 1 constructions for H0 = P5 with m ∈ {8, 9}. If the enumeration matches the figures and all bounds hold, the concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step is the assertion in Section 3 that “Such a (D0, τ0) is depicted in Figure 2(a,b) … Figure 2(c)” for all possible H0, together with the Figure 1 handling of H0 = P5 with m ∈ {8, 9}. The proof then derives the crucial inequality s(D,τ)(x) < s(D,τ)(y t−1) from properties attributed to these figures: a1 ≥ 2, a2 = 4 only when m1 = 0 and (D0, τ0) is Figure 2(i), and in the H0 = P5 subcase with |N t−1| = n−t−1 the bounds b1 = 1, b2 ≤ 8 or n, and a i − b i ≥ n−7. None of these can be verified from the text-only version, because the argument does not list the H0 cases or give the orientations and labelings. In particular, H0 may be disconnected when r > 1, and for e(G[Y]) = 3 the attachment of the external edge to an endpoint or to an internal vertex of P4 produces qualitatively different H0; the exhaustiveness of Figures 2(g,h,i) is precisely the claim that all such cases are covered. If any H0 is omitted, or if any displayed labeling violates the stated bounds, the ordering s(x) < s(y t−1) can fail and the theorem is not proved. This is not a defect in the reduction machinery: Lemmas 2.1–2.3 and the label-assignment arithmetic are internally consistent conditional on the figure claims.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies antimagic orientations of connected graphs, i.e., orientations equipped with a bijective edge labeling such that the incoming-minus-outgoing label sums at the vertices are pairwise distinct. The main result, Theorem 1.2, states that every connected graph on n≥9 vertices with maximum degree at least n−5 admits an antimagic orientation: part (i) covers Δ≥n−3 and part (ii) covers Δ=n−4 or n−5. The proof uses Euler tours to construct orientations with bounded vertex sums (Lemma 2.1), a lemma for graphs whose non-neighborhood of a maximum-degree vertex is independent (Lemma 2.2), a theorem for graphs with a dominating pair (Theorem 2.3), and then a reduction in Section 3 in which the remaining graphs are decomposed into a small subgraph H0 on Y∪{z_i}, the bipartite edges from Y to N(x), and the induced subgraph on N(x). The intended ordering of vertex sums is enforced by assigning small labels to Y and large labels to N(x). The decisive case analysis, however, is delegated to Figures 1 and 2, which are not included in the version under review.","tokens_in":10102,"tokens_out":24892,"duration_ms":233173,"significance":"If the case analysis is completed, the result is a genuine advance: it extends the previously known Δ≥n−3 threshold to Δ≥n−5 for n≥9 and gives further evidence for the Hefetz–Mütze–Schwartz conjecture that every connected graph admits an antimagic orientation. The Euler-tour lemma and the overall decomposition into H0, H1, and H2 are elegant and largely checkable, and the arithmetic after the figures is compatible with the stated bounds. The proof is self-contained and does not rely on the conjecture or on numerical fitting. The main weakness is that the decisive finite case analysis is contained entirely in the two figures, so the central claim of Theorem 1.2(ii) is not independently verifiable from the text as it stands.","major_comments":[{"comment":"The proof of Theorem 1.2(ii) is not checkable in the version under review because Figures 1 and 2 are referenced but not included, and the text does not otherwise specify the orientations and labelings (D0,τ0) that are asserted to exist. The subsequent argument depends on exactly those figure details at several load-bearing points: the bounds −4≤s(D0,τ0)(yi)≤0 and the pairwise separation |s(D0,τ0)(yi)−s(D0,τ0)(yj)|≤4; the facts a1≥2, and a2=4 only when m1=0 and (D0,τ0) is Figure 2(i); the inequalities q*<a2 for H0≠P5 and q*<a3 for H0=P5; and, in the H0=P5 subcase, b1=1, b2≤8 or n, and ai−bi≥n−7, together with the implicit s0(y4)=0 in the displayed expression for s(y4)−s(x). Since these are the only facts that make the final inequality s(x)<s(y_{t−1}) hold, the manuscript must include the figures or a table enumerating every possible H0 (including disconnected H0 and the two attachment positions for the connector on P4) with the corresponding (D0,τ0), and must state the numeric bounds case by case.","section":"Section 3, paragraphs referencing Figures 1 and 2"},{"comment":"There is a notation issue that affects the case analysis. If z1 is chosen adjacent to a vertex of degree two in G[Y]=P4, then the graph H0 is not the path P5; it has a degree-3 vertex. Thus the sentence 'Hence, the statement holds when H0=P5' does not cover the preferred choice just made. Please clarify whether Figure 1 and Figure 2(i) are meant to cover both the endpoint attachment (which yields H0=P5) and the internal attachment, and whether the name 'P5' is being used for the latter; otherwise one of the two attachment cases may be missing.","section":"Section 3, paragraph beginning 'Note that if G[Y]=P4...'"}],"minor_comments":[{"comment":"The displayed upper bounds for s(D,τ)(x), namely −(a1+1+2)−(n−t−1)a2 for H0≠P5 and −(a1+a2+1)−(n−t−2)a3 for H0=P5, are not self-evident. They follow from a_i≥a2+(i−2) (respectively a_i≥a3+(i−3)) together with n−t≥4, but this derivation should be written out so that the reader can check the lower bound on Σa_i.","section":"Section 3, displayed inequality for s(D,τ)(x)"},{"comment":"The phrase 'orienting the edge xx1 away from the vertex y' and similar expressions are ambiguous; 'away from' should be defined consistently as meaning that the named vertex is the tail, or the wording should be replaced by explicit tail/head notation.","section":"Theorem 2.3, second case"},{"comment":"The sentence mentioning Yilma's result could be made more precise by noting that Theorem 1.2(i) removes the lower bound Δ≥n−3≥6 from the known result, which helps the reader see the incremental contribution.","section":"Introduction, paragraph on Hartsfield–Ringel conjecture"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing you should know: this is a real, incremental result—connected graphs with Δ ≥ n−5 admit antimagic orientations—but the proof’s foundation is a case analysis that as submitted lives entirely in Figures 1 and 2, which are not in the text-only version. I cannot check it, and neither can you from this file.\n\nWhat is genuinely new: prior work covered regular and biregular bipartite graphs, and via Yilma’s labeling result one gets orientations for Δ ≥ n−3. This paper pushes the range to n−5. The technique is the established Eulerian orientation method, used more carefully. Lemmas 2.1–2.3 look right. The final inequality chain in Section 3 is detailed and checkable, conditional on the (D0, τ0) bounds. There is no circular reasoning, no parameter fitting, and the citations are standard. So the architecture of the proof is sound.\n\nThe soft spot is not subtle. The assertion that for every possible H0 (with e(G[Y]) = 1, 2, 3, 4, and the special P5 cases) there is a D0, τ0 with −4 ≤ s(y_i) ≤ 0 and pairwise sums separated by at most 4 is simply “depicted in Figure 2.” The text does not enumerate the cases, nor give the labelings. If any case is missing or mislabeled, the strict inequality s(x) < s(y_{t−1}) can fail. This is load-bearing. It is also fixable: the authors need to put the figure contents into the text or an appendix, and ideally give the small case tables. The reduction that produces H0 is also terse—choosing z_i, e_i, and the claim of exhaustiveness—but that part is standard and likely fine.\n\nMy verdict is conditional with moderate confidence: if the figures are correct and exhaustive, the theorem is proved. The paper deserves peer review, not desk rejection; the referee should demand the explicit case list. It is the kind of paper that is useful to the graph labeling community, and I would cite it if the case analysis checks out, but not until then.","headline":"Genuine incremental advance on antimagic orientations, but the proof's pivotal case analysis is hidden in missing figures; I would not accept the theorem as verified until that is fixed.","tokens_in":10637,"tokens_out":3912,"would_cite":false,"duration_ms":34866,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C78","05C20"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that every connected graph $G$ on $n\\ge 9$ vertices with maximum degree at least $n-5$ admits an antimagic orientation: an orientation together with a bijection from the arcs to $\\{1,2,\\ldots,m\\}$ such that every vertex…","keywords":["antimagic labeling","antimagic orientation","maximum degree","Euler tour","vertex-sum","graph labeling","digraph labeling"],"falsifier":"Enumerate all connected graphs on $n=9$ vertices with maximum degree $4$, the smallest nontrivial case $\\Delta=n-5$, and search each for an antimagic orientation by brute force; a single graph with no such orientation would refute Theorem 1.2. A sharper check targets the load-bearing step: enumerate every possible $H_0$ with $1\\le \\Delta(G[Y])\\le 2$ and test whether any admits no pair $(D_0,\\tau_0)$ with sums in $[-4,0]$ and pairwise distance at most $4$.","tokens_in":9554,"feed_emoji":"🧩","tokens_out":10432,"duration_ms":88242,"temperature":0.7,"pith_summary":"This paper proves that every connected graph $G$ on $n\\ge 9$ vertices with maximum degree at least $n-5$ admits an antimagic orientation: an orientation together with a bijection from the arcs to $\\{1,2,\\ldots,m\\}$ such that every vertex has a distinct vertex-sum, where the vertex-sum is the sum of labels on incoming arcs minus the sum of labels on outgoing arcs. This verifies the 2010 antimagic-orientation conjecture for graphs close to having a universal vertex, extending the known families beyond regular and biregular bipartite graphs. The proof chooses a maximum-degree vertex $x$, handles the few vertices outside its closed neighborhood with explicit small patterns, and uses an Euler-tour lemma to orient the rest so that the vertex-sums fall into a strict order.","feed_headline":"Graphs with max degree n−5 are antimagic-orientable","feed_subtitle":"The theorem covers n≥9 and Δ≥n−5, supporting the 2010 conjecture for all connected graphs.","key_machinery":"The engine is an Euler-tour lemma: given any graph and prescribed label values $a_1<\\cdots<a_m$, one can orient the graph and assign these labels so that every vertex-sum is at least $-a_m$. The main proof applies this to the subgraph induced by $N(x)$ and to the part left after removing $x$ and $Y:=V(G)\\setminus N[x]$. The small remainder $H_0$, built from $Y$ plus one attachment edge from a chosen neighbor of $x$, is settled by the finite case list in Figures 1 and 2: an injective labeling of its arcs with numbers from $\\{1,\\ldots,6\\}$ (or $\\{1,\\ldots,6,10\\}$ when $H_0=P_5$) gives sums in $[-4,0]$ with pairwise distances at most $4$. The orientation of the remaining edges then layers the unused labels, keeps the $Y$-sums strictly decreasing, and gives $x$ the unique most negative sum.","core_discovery":"The central result is Theorem 1.2: a connected graph $G$ has an antimagic orientation if $\\Delta(G)\\ge |G|-3$, and also if $\\Delta(G)=|G|-t\\ge 4$ for each $t\\in\\{4,5\\}$. Equivalently, every connected graph on $n\\ge 9$ vertices with maximum degree at least $n-5$ admits an antimagic orientation. The proof is constructive: for the small subgraph induced by the vertices outside the closed neighborhood of a maximum-degree vertex, the authors write down orientations and labelings whose vertex-sums lie in $[-4,0]$ and are pairwise distinct; the remaining edges are labeled in four layers, with an Euler-tour argument keeping the sums of the other high-degree vertices positive and ordered, so the final inequality chain $s(x)<s(y_{t-1})<\\cdots<s(y_1)\\le 0<s(v_1)<\\cdots<s(v_{n-t})$ certifies that all vertex-sums are distinct.","pith_inferences":["One could push the same method toward $\\Delta=n-6$: the Euler-tour step is generic, so the missing ingredient is only a larger finite list of $H_0$ patterns, which computer search can supply.","The construction is algorithmic in the dense range: after tabulating the small patterns, labels are assigned by degree order and Euler tours, so an antimagic orientation can be produced in time linear in the number of edges.","Because the paper's case analysis is finite and explicit, the $t=4,5$ part of Theorem 1.2 could be independently checked by machine verification of Figures 1 and 2, converting the proof into a formal certificate."],"forward_implications":["For every connected graph on $n\\ge 9$ vertices with $\\Delta(G)\\ge n-5$, an antimagic orientation exists, and the proof gives an explicit way to construct it.","The range $\\Delta(G)\\ge |G|-3$, previously known for antimagic labelings, now also holds for antimagic orientations as part (i) of Theorem 1.2.","Every complete multipartite graph admits an antimagic orientation, since its vertices include a pair whose closed neighborhoods cover the graph (Theorem 2.3).","The 2010 conjecture is verified for a new dense family: connected graphs in which some vertex is adjacent to all but at most four other vertices."],"supporting_citations":[{"why":"introduces antimagic orientations and Conjecture 1.1, and contributes the Eulerian-orientation strategy used throughout","marker":"[9]"},{"why":"proves antimagic labelings for graphs with maximum degree at least n-3, motivating the same large-degree regime here","marker":"[13]"},{"why":"verifies antimagic orientations of even regular graphs by Euler tours, the technique the present proof adapts","marker":"[10]"},{"why":"gives a follow-up on even regular graphs that refines the Eulerian method","marker":"[12]"},{"why":"verifies Conjecture 1.1 for biregular bipartite graphs, the immediate previous frontier this paper extends","marker":"[11]"},{"why":"introduces antimagic labelings and the original 1990 conjecture that motivates the digraph version","marker":"[8]"}],"fun_headline_variants":["Antimagic orientation guaranteed for max degree ≥ n−5","Graphs with Δ≥n−5 admit antimagic orientations","Near-complete graphs all have antimagic orientations","New result: Δ≥n−5 implies antimagic orientability","For n≥9, max degree n−5 forces antimagic orientation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof of the $t=4,5$ case depends on the claim that Figures 1 and 2 list every possible small leftover subgraph $H_0$ and that the depicted labelings satisfy the asserted bounds $-4\\le s(y_i)\\le 0$ with pairwise sums differing by at most $4$; if one possible $H_0$ is missing or one labeling violates its bound, the final inequality chain can fail.","fun_headline_variants_meta":{"raw":{"variants":["Antimagic orientation guaranteed for max degree ≥ n−5","Graphs with Δ≥n−5 admit antimagic orientations","Near-complete graphs all have antimagic orientations","New result: Δ≥n−5 implies antimagic orientability","For n≥9, max degree n−5 forces antimagic orientation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000236,"raw_usage":{"total_tokens":1539,"prompt_tokens":1016,"completion_tokens":523,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":632,"completion_tokens_details":{"reasoning_tokens":433}},"tokens_in":632,"tokens_out":523,"duration_ms":4740,"temperature":1.0,"reasoning_tokens":433,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:57:50.881710+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all connected graphs on $n=9$ vertices with maximum degree $4$, the smallest nontrivial case $\\Delta=n-5$, and search each for an antimagic orientation by brute force; a single graph with no such orientation would refute Theorem 1.2. A sharper check targets the load-bearing step: enumerate every possible $H_0$ with $1\\le \\Delta(G[Y])\\le 2$ and test whether any admits no pair $(D_0,\\tau_0)$ with sums in $[-4,0]$ and pairwise distance at most $4$.","supporting_citations":[{"cited_title":"Hefetz, T","cited_arxiv_id":null,"evidence_quote":"introduces antimagic orientations and Conjecture 1.1, and contributes the Eulerian-orientation strategy used throughout"},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"proves antimagic labelings for graphs with maximum degree at least n-3, motivating the same large-degree regime here"},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"verifies antimagic orientations of even regular graphs by Euler tours, the technique the present proof adapts"},{"cited_title":"Yang, A note on antimagic orientations of even regular graphs, to appear in Discrete Appl","cited_arxiv_id":null,"evidence_quote":"gives a follow-up on even regular graphs that refines the Eulerian method"},{"cited_title":"Shan and X","cited_arxiv_id":null,"evidence_quote":"verifies Conjecture 1.1 for biregular bipartite graphs, the immediate previous frontier this paper extends"},{"cited_title":"Hartsfield and G","cited_arxiv_id":null,"evidence_quote":"introduces antimagic labelings and the original 1990 conjecture that motivates the digraph version"}],"review_version":1}