Graphs of large linear size are antimagic

DOI10.1002/JGT.21872MaRDI QIDQ2800541zbMATH OpenOpenAlexFDO

Authors Tom Eccles

Publication date 15 April 2016

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

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

zbMATH Keywords

antimagiclabelling

Mathematics Subject Classification ID

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

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$.

Recommendations

• Dense graphs are antimagic
• Anti‐magic graphs via the Combinatorial NullStellenSatz
• Regular graphs of odd degree are antimagic
• Antimagic properties of graphs with large maximum degree
• Proof of a local antimagic conjecture

Cites work

• k-tuple total domination in graphs
• A dynamic survey of graph labeling
• An application of the combinatorial nullstellensatz to a graph labelling problem
• Anti‐magic graphs via the Combinatorial NullStellenSatz
• Dense graphs are antimagic
• Dominating a family of graphs with small connected subgraphs
• scientific article; zbMATH DE number 47933 (Why is no real title available?)
• Regular bipartite graphs are antimagic

Cited in

(28)

• Antimagic orientation of biregular bipartite graphs
• Local antimagic orientations of \(d\)-degenerate graphs
• Partially magic labelings and the antimagic graph conjecture
• A generalized version of a local antimagic labelling conjecture
• Caterpillars with maximum degree 3 are antimagic
• Antimagic orientations of graphs with large maximum degree
• Antimagic labelings of caterpillars
• Antimagic labeling of biregular bipartite graphs
• Antimagic labeling of some biregular bipartite graphs
• Caterpillars are antimagic
• A note on antimagic orientations of even regular graphs
• Antimagic orientation of Halin graphs
• Antimagic orientations of graphs with given independence number
• On local antimagic chromatic number of graphs
• List-antimagic labeling of vertex-weighted graphs
• Local antimagic chromatic number for the corona product of wheel and null graphs
• Local vertex antimagic chromatic number of some wheel related graphs
• Antimagic orientation of graphs with minimum degree at least 33
• Antimagic orientation of forests
• Approaches that output infinitely many graphs with small local antimagic chromatic number
• Graph antimagic labeling: a survey
• On local antimagic chromatic number of cycle-related join graphs. II
• Antimagic and product antimagic graphs with pendant edges
• Antimagic labeling of subdivided caterpillars
• Beyond biregular: antimagicness of uni-regular bipartite graphs
• Bipartite graphs with minimum degree at least 15 are antimagic
• Construction of the 1-skeleton of the A₄-structure of a graph with antimagic labeling and its application to social network analysis
• Antimagic orientation of subdivided caterpillars

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)