Dense graphs are antimagic

DOI10.1002/JGT.20027MaRDI QIDQ3159384zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

antimagic labeling

Mathematics Subject Classification ID

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

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.

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

Cited in

(82)

• On vertex in-out-antimagic total digraphs
• 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
• On the Hartsfield-Ringel hypothesis: connected unigraphs
• Antimagic labeling of the lexicographic product graph \(K_{m,n}[P_k]\)
• A class of antimagic join graphs
• Generation of anti-magic graphs from binary graph products
• Antimagicness of generalized corona and snowflake graphs
• Antimagic labeling and canonical decomposition of graphs
• On local antimagic chromatic number of cycle-related join graphs. II
• Local antimagic orientations of \(d\)-degenerate graphs
• Construction of antimagic labeling for the Cartesian product of regular graphs
• Antimagic orientation of graphs with minimum degree at least 33
• Antimagic labeling for some snake graphs
• Antimagic labeling of biregular bipartite graphs
• Caterpillars with maximum degree 3 are antimagic
• Antimagic labelings of caterpillars
• scientific article; zbMATH DE number 7593805 (Why is no real title available?)
• The antimagicness of the Cartesian product of graphs
• A new class of antimagic Cartesian product graphs
• Antimagic labeling of generalized pyramid graphs
• Antimagic labelings of join graphs
• Local antimagic orientation of graphs
• Partially magic labelings and the antimagic graph conjecture
• Regular bipartite graphs are antimagic
• 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
• Stacked book graphs are cycle-antimagic
• A generalized version of a local antimagic labelling conjecture
• Local antimagic labeling of graphs
• 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
• On \(k\)-shifted antimagic spider forests
• Approaches that output infinitely many graphs with small local antimagic chromatic number
• Weighted antimagic labeling: an algorithmic approach
• Antimagic orientations of graphs with given independence number
• An antimagic labeling in \(K_{2n,2n} - nC_4\)
• Shifted-antimagic labelings for graphs
• Graphs of large linear size are antimagic
• On \((a, 1)\)-vertex-antimagic edge labeling of regular graphs
• Antimagic orientation of forests
• Anti‐magic graphs via the Combinatorial NullStellenSatz
• Antimagic labeling of cubic graphs
• Graphs admitting antimagic labeling for arbitrary sets of positive integers
• On anti-magic labeling for graph products
• On antimagic directed graphs
• Magic squares and antimagic graphs
• Finding Antimagic Labelings of Trees by Evolutionary Search
• Lattice grids and prisms are antimagic
• Regular graphs of odd degree are antimagic
• Antimagicness of tensor product for some wheel related graphs with star
• Antimagic labeling of forests
• 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
• On edge-graceful regular graphs with particular 3-factors
• Antimagic labeling for subdivisions of graphs
• Labeling trees of small diameters with consecutive integers
• Antimagic labeling for unions of graphs with many three-paths
• Bertrand's postulate, the prime number theorem and product anti-magic graphs
• Graph antimagic labeling: a survey
• Multi-bridge graphs are anti-magic
• Lexicographic product graphs \(P_m[P_n]\) are antimagic
• Approximate results for rainbow labelings

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)