×

On antimagic directed graphs. (English) Zbl 1209.05213

Summary: An antimagic labeling of an undirected graph \(G\) with \(n\) vertices and \(m\) edges is a bijection from the set of edges of \(G\) to the integers \(\{1, \dots , m\}\) such that all \(n\) vertex sums are pairwise distinct, where a vertex sum is the sum of labels of all edges incident with that vertex. A graph is called antimagic if it admits an antimagic labeling. In N. Hartsfield and G. Ringel, Pearls in Graph Theory (1990; Zbl 0703.05001), pp. 108–109), Hartsfield and Ringel conjectured that every simple connected graph, other than \(K_{2}\), is antimagic. Despite considerable effort in recent years, this conjecture is still open. In this article we study a natural variation; namely, we consider antimagic labelings of directed graphs. In particular, we prove that every directed graph whose underlying undirected graph is “dense” is antimagic, and that almost every undirected \(d\)-regular graph admits an orientation which is antimagic.

MSC:

05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C20 Directed graphs (digraphs), tournaments

Citations:

Zbl 0703.05001
Full Text: DOI

References:

[1] Alon, Dense graphs are antimagic, J Graph Theory 47 pp 297– (2004) · Zbl 1055.05132
[2] Bollobás, Random Graphs (2001) · doi:10.1017/CBO9780511814068
[3] Cranston, Regular bipartite graphs are antimagic, J Graph Theory 60 pp 173– (2009) · Zbl 1210.05141
[4] Diestel, Graph Theory (2005)
[5] Gallian, A dynamic survey of graph labeling, Electron J Combin (19972009) · Zbl 0953.05067
[6] Hartsfield, Pearls in Graph Theory pp 108– (1990) · Zbl 0703.05001
[7] Hefetz, Anti-magic graphs via the Combinatorial Nullstellensatz, J Graph Theory 50 pp 263– (2005) · Zbl 1076.05068
[8] Hefetz, An application of the Combinatorial Nullstellensatz to a graph labelling problem, J Graph Theory · Zbl 1209.05214
[9] Kaplan, On zero-sum partitions and anti-magic trees,, Discrete Math 309 pp 2010– (2009) · Zbl 1229.05031
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.