← Back to arXiv
arXivCombinatoricsarXiv:2608.00209

Antimagic orientations of graphs with a dominating clique

The paper studies a mathematical property of graphs (networks of nodes connected by edges). The specific property is called an "antimagic orientation." To create one, you assign a unique number to each edge and also give each edge a direction (turning it into an arrow). Then, for every node, you calculate a score by adding up the numbers on arrows pointing into it and subtracting the numbers on arrows pointing out of it. The orientation is "antimagic" if all these scores are different from one another across all nodes.

A conjecture by Hefetz, Mutze, and Schwartz claims that every connected graph can be given an antimagic orientation. This is a long-standing open problem, and researchers have been proving it holds for specific families of graphs as a way of building toward the full result. The challenge is that the combination of choosing directions and choosing labels creates an enormous space of possibilities, making it hard to guarantee a valid assignment exists for arbitrary graphs.

This paper proves the conjecture is true for a particular class of graphs: those containing a "dominating clique." A clique is a subset of nodes where every pair is directly connected, and it is dominating when every other node in the graph is directly connected to at least one member of this clique. In other words, the clique sits centrally enough that it "reaches" the entire graph. The authors develop a constructive approach that exploits this central structure to carefully assign labels and directions, guaranteeing all vertex scores turn out distinct. This adds another meaningful family of graphs to the list for which the conjecture is confirmed.

Read original →