Graphs of large linear size are antimagic

DOI10.1002/JGT.21872zbMATH Open1333.05264arXiv1409.3659OpenAlexW1902759194MaRDI QIDQ2800541FDOQ2800541

Tom Eccles

Publication date: 15 April 2016

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

Abstract: Given a graph $G=(V,E)$ and a colouring $f:EmapstomathbbN$, the induced colour of a vertex $v$ is the sum of the colours at the edges incident with $v$. If all the induced colours of vertices of $G$ are distinct, the colouring is called antimagic. If $G$ has a bijective antimagic colouring $f:Emapsto1,dots,|E|$, the graph $G$ is called antimagic. A conjecture of Hartsfield and Ringel states that all connected graphs other than $K_2$ are antimagic. Alon, Kaplan, Lev, Roddity and Yuster proved this conjecture for graphs with minimum degree at least $clog|V|$ for some constant $c$; we improve on this result, proving the conjecture for graphs with average degree at least some constant $d_0$.

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

zbMATH Keywords

labellingantimagic

Mathematics Subject Classification ID

Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• A dynamic survey of graph labeling
• \(k\)-tuple total domination in graphs
• An Application of the combinatorial Nullstellensatz to a graph labelling problem
• Dense graphs are antimagic
• Regular bipartite graphs are antimagic
• Title not available (Why is that?)
• Anti‐magic graphs via the Combinatorial NullStellenSatz
• Dominating a family of graphs with small connected subgraphs

Cited In (23)

• On local antimagic chromatic number of cycle-related join graphs. II
• Antimagic orientation of subdivided caterpillars
• Antimagic orientation of graphs with minimum degree at least 33
• Local antimagic orientations of \(d\)-degenerate graphs
• Antimagic labeling of biregular bipartite graphs
• Caterpillars with maximum degree 3 are antimagic
• Antimagic labelings of caterpillars
• Partially magic labelings and the antimagic graph conjecture
• ON LOCAL ANTIMAGIC CHROMATIC NUMBER OF GRAPHS
• Antimagic orientation of biregular bipartite graphs
• A generalized version of a local antimagic labelling conjecture
• Antimagic orientations of graphs with large maximum degree
• Caterpillars are antimagic
• A note on antimagic orientations of even regular graphs
• Antimagic orientation of Halin graphs
• Antimagic labeling of some biregular bipartite graphs
• Approaches that output infinitely many graphs with small local antimagic chromatic number
• List-antimagic labeling of vertex-weighted graphs
• Antimagic orientations of graphs with given independence number
• Antimagic orientation of forests
• Local antimagic chromatic number for the corona product of wheel and null graphs
• Local vertex antimagic chromatic number of some wheel related graphs
• Graph antimagic labeling: a survey

This page was built for publication: Graphs of large linear size are antimagic

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