Antimagic orientations of graphs with large maximum degree

Andrew Owens; Donglei Yang; Fangfang Zhang; Inne Singgih; Joshua Carlson; K. E. Perry; Xiaohong Zhang; Zi-Xia Song

REVIEW 2 major objections 3 minor 13 references

Antimagic orientations of graphs with large maximum degree

T0 review · 2 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read 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…

desk verdict 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. read the letter →

arxiv 1908.06072 v1 pith:HC457UDO submitted 2019-08-16 math.CO

Donglei Yang , Joshua Carlson , Andrew Owens , K. E. Perry , Inne Singgih , Zi-Xia Song , Fangfang Zhang , Xiaohong Zhang This is my paper · ORCID

classification math.CO MSC 05C7805C20

keywords antimagiclabelingorientationmaximumdegreeEulertourvertex-sumgraphdigraph

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

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.

What carries the argument

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.

What would settle it

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$.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

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

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the 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.

What 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.

The 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.

My 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.

Referee Report

2 major / 3 minor

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.

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 (2)

[Section 3, paragraphs referencing Figures 1 and 2] 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 3, paragraph beginning 'Note that if G[Y]=P4...'] 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.

minor comments (3)

[Section 3, displayed inequality for s(D,τ)(x)] 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.
[Theorem 2.3, second case] 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.
[Introduction, paragraph on Hartsfield–Ringel conjecture] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the proof is a direct construction using Euler tours and explicit label assignments; the figure-based case analysis is a verification gap, not a circular dependency.

full rationale

The paper's derivation is self-contained: Theorem 1.2 is proved by explicitly constructing an orientation D and a bijective labeling tau of the arcs, then verifying that the vertex-sums are totally ordered. The auxiliary results (Lemma 2.1, Lemma 2.2, Theorem 2.3) are proved directly from Euler's theorem and elementary counting; none of them assumes Conjecture 1.1 or the conclusion of Theorem 1.2. The construction assigns labels in stages (N0, N1, ..., Nt-1, N, then a1,...,a_{n-t}) and the final inequality chain is derived from explicit bounds on these labels. Citations to earlier antimagic orientation papers are used only as background or as sources for the conjecture and known special cases, not as load-bearing evidence for the new theorem. The proof does depend on the assertion that the orientations and labelings in Figures 1 and 2 exhaust all possible subgraphs H0 and satisfy the stated bounds, but this is a completeness/verifiability concern about a finite case analysis, not circular reasoning: the figures do not encode the theorem's conclusion, and the paper does not fit any parameter to the target result. Therefore no step reduces to its own input by construction, and the correct circularity score is 0.

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

The proof rests on Euler's theorem (standard) and on the completeness and correctness of the finite case analysis shown in the figures. No free parameters or invented entities are introduced.

assumptions (2)

standard math A connected multigraph admits an Euler tour if and only if every vertex has even degree.
Invoked in Lemma 2.1 to construct the orientation and labeling used throughout the paper.
ad hoc to paper The finite case analysis in Figures 1 and 2 exhaustively lists all possible subgraphs H0 with 1 <= Delta(G[Y]) <= t-3, and each depicted (D0, tau0) satisfies the asserted range and separation bounds.
The proof of Theorem 1.2(ii) depends on these bounds for the vertex sums on Y and on the specific label inequalities used for the H0=P5 case; this premise cannot be checked from the text alone.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Antimagic orientations of graphs with large maximum degree." pith.science (2026). https://pith.science/paper/HC457UDO

@misc{pith2026190806072,
  author       = {Pith},
  title        = {Pith review of: Antimagic orientations of graphs with large maximum degree},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HC457UDO}},
  note         = {Machine review of arXiv:1908.06072}
}

abstract

Given a digraph $D$ with $m $ arcs, a bijection $\tau: A(D)\rightarrow \{1, 2, \ldots, m\}$ is an antimagic labeling of $D$ if no two vertices in $D$ have the same vertex-sum, where the vertex-sum of a vertex $u $ in $D$ under $\tau$ is the sum of labels of all arcs entering $u$ minus the sum of labels of all arcs leaving $u$. We say $(D, \tau)$ is an antimagic orientation of a graph $G$ if $D$ is an orientation of $G$ and $\tau$ is an antimagic labeling of $D$. Motivated by the conjecture of Hartsfield and Ringel from 1990 on antimagic labelings of graphs, Hefetz, M\"{u}tze, and Schwartz in 2010 initiated the study of antimagic orientations of graphs, and conjectured that every connected graph admits an antimagic orientation. This conjecture seems hard, and few related results are known. However, it has been verified to be true for regular graphs and biregular bipartite graphs. In this paper, we prove that every connected graph $G$ on $n\ge9$ vertices with maximum degree at least $n-5$ admits an antimagic orientation.

Figures

Figures reproduced from arXiv: 1908.06072 by the authors.

**Figure 1.** Antimagic orientations of all possible G when H0 = P5 and m ∈ {8, 9}. Let m := e(G). Then m ≥ |G| − 1 ≥ t + 3. Note that if G[Y ] = P4, then Y1 = G[Y ], t = 5 and m ≥ t + 3 = 8. In this case, we choose z1 so that z1 is adjacent to a vertex of degree two in G[Y ] if possible. Hence, the statement holds when H0 = P5 and m ≤ 9, as depicted in [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗

**Figure 2.** (D0, τ0) of all possible H0 according to e(G[Y ]). For i, j ∈ [t − 1] with i 6= j, we define yi ≺ yj if either dH1 (yi) < dH1 (yj ), or dH1 (yi) = dH1 (yj ) and s(D0,τ0) (yi) > s(D0,τ0) (yj ). This is possible because s(D0,τ0) (y1), . . . , s(D0,τ0) (yt−1) are pairwise distinct. We may assume that y1 ≺ y2 ≺ · · · ≺ yt−1. Let N0 := τ0(A(D0)), N1 be the set (possibly empty) of dH1 (y1) many smallest numbers in {5, . .… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

[1]

N. Alon, G. Kaplan, A. Lev, Y. Roditty, and R. Yuster, Dense graphs are antimagic, J. Graph Theory 47 (2004), 297-309. 10

work page 2004
[2]

B´ erczi, A

K. B´ erczi, A. Bern´ ath, and M. Vizer, Regular graphs are antimagic, Electron. J. Combin. 22 (2015): Paper 3.34

work page 2015
[3]

Chang, Y-C

F. Chang, Y-C. Liang, Z. Pan, and X. Zhu, Antimagic labeling of regular graphs, J. Graph Theory 82 (2016), 339–349

work page 2016
[4]

Cranston, Regular bipartite graphs are antimagic, J

D. Cranston, Regular bipartite graphs are antimagic, J. Graph Theory 60 (2009) 173–182

work page 2009
[5]

D. W. Cranston, Y-C. Liang, and X. Zhu, Regular graphs of odd degree are antimagic, J. Graph Theory 80 (2015) 28–33

work page 2015
[6]

Eccles, Graphs of large linear size are antimagic, J

T. Eccles, Graphs of large linear size are antimagic, J. Graph Theory 81 (2016) 236–261

work page 2016
[7]

J. A. Gallian, A dynamic survey of graph labeling, Electron J. Combin DS6 (2016)

work page 2016
[8]

Hartsﬁeld and G

N. Hartsﬁeld and G. Ringel, Pearls in Graph Theory, Academic Press, Boston, (1990) 108-109 (revised version, 1994)

work page 1990

Show all 13 references

[9]

Hefetz, T

D. Hefetz, T. M¨ utze, and J. Schwartz, On antimagic directed graphs, J. Graph Theory 64 (2010) 219–232

2010
[10]

T. Li, Z-X. Song, G. Wang, D. Yang, and C-Q. Zhang, Antimagic orientations of even regular graphs, J. Graph Theory 90 (2019) 46–53

2019
[11]

Shan and X

S. Shan and X. Yu, Antimagic orientation of biregular bipartite graphs, Electron. J. Combin. 24 (2017): Paper 4.31

2017
[12]

Yang, A note on antimagic orientations of even regular graphs, to appear in Discrete Appl

D. Yang, A note on antimagic orientations of even regular graphs, to appear in Discrete Appl. Math. (https://doi.org/10.1016/j.dam.2019.04.017)

2019 doi
[13]

Z. B. Yilma, Antimagic properties of graphs with large maximum degree, J. Graph Theory 72 (2013) 367–373. 11

2013

Pith tools

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

[1] [1]

N. Alon, G. Kaplan, A. Lev, Y. Roditty, and R. Yuster, Dense graphs are antimagic, J. Graph Theory 47 (2004), 297-309. 10

work page 2004

[2] [2]

B´ erczi, A

K. B´ erczi, A. Bern´ ath, and M. Vizer, Regular graphs are antimagic, Electron. J. Combin. 22 (2015): Paper 3.34

work page 2015

[3] [3]

Chang, Y-C

F. Chang, Y-C. Liang, Z. Pan, and X. Zhu, Antimagic labeling of regular graphs, J. Graph Theory 82 (2016), 339–349

work page 2016

[4] [4]

Cranston, Regular bipartite graphs are antimagic, J

D. Cranston, Regular bipartite graphs are antimagic, J. Graph Theory 60 (2009) 173–182

work page 2009

[5] [5]

D. W. Cranston, Y-C. Liang, and X. Zhu, Regular graphs of odd degree are antimagic, J. Graph Theory 80 (2015) 28–33

work page 2015

[6] [6]

Eccles, Graphs of large linear size are antimagic, J

T. Eccles, Graphs of large linear size are antimagic, J. Graph Theory 81 (2016) 236–261

work page 2016

[7] [7]

J. A. Gallian, A dynamic survey of graph labeling, Electron J. Combin DS6 (2016)

work page 2016

[8] [8]

Hartsﬁeld and G

N. Hartsﬁeld and G. Ringel, Pearls in Graph Theory, Academic Press, Boston, (1990) 108-109 (revised version, 1994)

work page 1990