Dense graphs are antimagic

DOI10.1002/JGT.20027zbMATH Open1055.05132arXivmath/0304198OpenAlexW2949865692MaRDI QIDQ3159384FDOQ3159384

Authors: Noga Alon, Gil Kaplan, Arieh Lev, Raphael Yuster, Yehuda Roditty 

Publication date: 16 February 2005

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: An {em antimagic labeling} of a graph with $m$ edges and $n$ vertices is a bijection from the set of edges to the integers $1,\mathrm{...},m$ such that all $n$ vertex sums are pairwise distinct, where a vertex sum is the sum of labels of all edges incident with the same vertex. A graph is called {em antimagic} if it has an antimagic labeling. A conjecture of Ringel (see cite{HaRi}) states that every connected graph, but $K_2$, is antimagic. Our main result validates this conjecture for graphs having minimum degree $Omega(logn)$. The proof combines probabilistic arguments with simple tools from analytic number theory and combinatorial techniques. We also prove that complete partite graphs (but $K_2$) and graphs with maximum degree at least $n-2$ are antimagic.

Full work available at URL: https://arxiv.org/abs/math/0304198

Recommendations

• On antimagic directed graphs
• On anti-magic labeling for graph products
• A class of antimagic join graphs
• Antimagic properties of graphs with large maximum degree

zbMATH Keywords

antimagic labeling

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• Title not available (Why is that?)

Cited In (82)

• On antimagic labeling of regular graphs with particular factors
• Anti-magic labeling of trees
• Antimagic labeling graphs with a regular dominating subgraph
• Antimagic orientation of subdivided caterpillars
• Antimagic labeling of the lexicographic product graph \(K_{m,n}[P_k]\)
• A class of antimagic join graphs
• Antimagic orientation of graphs with minimum degree at least 33
• Antimagicness of generalized corona and snowflake graphs
• Antimagic labeling and canonical decomposition of graphs
• Local antimagic orientations of \(d\)-degenerate graphs
• Construction of antimagic labeling for the Cartesian product of regular graphs
• Antimagic labeling of biregular bipartite graphs
• Caterpillars with maximum degree 3 are antimagic
• Antimagic labelings of caterpillars
• The antimagicness of the Cartesian product of graphs
• Antimagic labeling of generalized pyramid graphs
• A new class of antimagic Cartesian product graphs
• Antimagic labelings of join graphs
• Local antimagic orientation of graphs
• Regular bipartite graphs are antimagic
• Partially magic labelings and the antimagic graph conjecture
• Weighted-1-antimagic graphs of prime power order
• Antimagic orientation of biregular bipartite graphs
• Characterization of product anti-magic graphs of large order
• Labelings of plane graphs containing Hamilton path
• Local antimagic labeling of graphs
• A generalized version of a local antimagic labelling conjecture
• On zero-sum partitions and anti-magic trees
• Antimagic labeling of forests with sets of consecutive integers
• Antimagic orientations of graphs with large maximum degree
• Antimagicness of lexicographic product graph \(G[P_n]\)
• On a relationship between completely separating systems and antimagic labeling of regular graphs
• Antimagic labeling of regular graphs
• Vertex-antimagic labelings of regular graphs
• Caterpillars are antimagic
• Antimagic orientations for the complete \(k\)-ary trees
• Sparse graphs with vertex antimagic edge labelings
• Antimagic orientations of disconnected even regular graphs
• A note on antimagic orientations of even regular graphs
• Antimagic orientation of Halin graphs
• Antimagic labeling of some biregular bipartite graphs
• Weighted antimagic labeling: an algorithmic approach
• Graphs of large linear size are antimagic
• Shifted-antimagic labelings for graphs
• On \((a, 1)\)-vertex-antimagic edge labeling of regular graphs
• Anti‐magic graphs via the Combinatorial NullStellenSatz
• Antimagic labeling of cubic graphs
• Graphs admitting antimagic labeling for arbitrary sets of positive integers
• Magic squares and antimagic graphs
• On antimagic directed graphs
• On anti-magic labeling for graph products
• Lattice grids and prisms are antimagic
• Regular graphs of odd degree are antimagic
• Graphs admitting antimagic labeling for arbitrary sets of positive numbers
• Antimagic labelling of vertex weighted graphs
• Weighted antimagic labeling
• An application of the combinatorial nullstellensatz to a graph labelling problem
• Antimagic properties of graphs with large maximum degree
• Bertrand's postulate, the prime number theorem and product anti-magic graphs
• Lexicographic product graphs \(P_m[P_n]\) are antimagic
• Approximate results for rainbow labelings
• On vertex in-out-antimagic total digraphs
• On the Hartsfield-Ringel hypothesis: connected unigraphs
• Generation of anti-magic graphs from binary graph products
• On local antimagic chromatic number of cycle-related join graphs. II
• Antimagic labeling for some snake graphs
• Title not available (Why is that?)
• Stacked book graphs are cycle-antimagic
• On \(k\)-shifted antimagic spider forests
• Approaches that output infinitely many graphs with small local antimagic chromatic number
• Antimagic orientations of graphs with given independence number
• An antimagic labeling in \(K_{2n,2n} - nC_4\)
• Antimagic orientation of forests
• Finding Antimagic Labelings of Trees by Evolutionary Search
• Antimagicness of tensor product for some wheel related graphs with star
• Antimagic labeling of forests
• Antimagic labeling for subdivisions of graphs
• Labeling trees of small diameters with consecutive integers
• On edge-graceful regular graphs with particular 3-factors
• Graph antimagic labeling: a survey
• Antimagic labeling for unions of graphs with many three-paths
• Multi-bridge graphs are anti-magic

This page was built for publication: Dense graphs are antimagic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3159384)