Publication:2223075

DOI10.1007/S00009-020-01688-ZzbMATH Open1456.05138arXiv1812.06715OpenAlexW3122254133MaRDI QIDQ2223075FDOQ2223075

Antoni Lozano, Joaquín Tey, Carlos Seara, Mercè Mora

Publication date: 28 January 2021

Published in: Mediterranean Journal of Mathematics (Search for Journal in Brave)

Abstract: An antimagic labeling of a graph $G$ is an injection from $E(G)$ to $1,2,dots,|E(G)|$ such that all vertex sums are pairwise distinct, where the vertex sum at vertex $u$ is the sum of the labels assigned to edges incident to $u$. A graph is called antimagic when it has an antimagic labeling. Hartsfield and Ringel conjectured that every simple connected graph other than $K_2$ is antimagic and the conjecture remains open even for trees. Here we prove that caterpillars are antimagic by means of an $O(nlogn)$ algorithm.

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

zbMATH Keywords

algorithmscaterpillarsantimagic

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• A dynamic survey of graph labeling
• On zero-sum partitions and anti-magic trees
• Combinatorial Nullstellensatz
• Lattice grids and prisms are antimagic
• Dense graphs are antimagic
• Regular bipartite graphs are antimagic
• Antimagic Properties of Graphs with Large Maximum Degree
• Anti‐magic graphs via the Combinatorial NullStellenSatz
• Computing and Combinatorics
• On anti-magic labeling for graph products
• The antimagicness of the Cartesian product of graphs
• Antimagic labeling of cubic graphs
• On antimagic directed graphs
• Antimagic Labeling of Regular Graphs
• Anti-magic labeling of trees
• A new class of antimagic Cartesian product graphs
• Approximate results for rainbow labelings
• Regular graphs are antimagic
• Graphs of large linear size are antimagic
• Regular Graphs of Odd Degree Are Antimagic
• Antimagic labeling of generalized pyramid graphs
• Caterpillars with maximum degree 3 are antimagic
• Antimagic labelings of caterpillars
• Caterpillars Have Antimagic Orientations

Cited In (15)

• Antimagic orientation of subdivided caterpillars
• Every graph is homeomorphic to an antimagic bipartite graph
• Perfectly antimagic total labeling of star-like trees and the corona product of two graphs
• Antimagic labelings of caterpillars
• Product antimagic labeling of caterpillars
• Title not available (Why is that?)
• On \(k\)-shifted antimagic spider forests
• Antimagic labeling of some biregular bipartite graphs
• List-antimagic labeling of vertex-weighted graphs
• Trees whose even-degree vertices induce a path are antimagic
• Antimagic orientation of forests
• Finding Antimagic Labelings of Trees by Evolutionary Search
• Title not available (Why is that?)
• Graph antimagic labeling: a survey
• Antimagic labeling for unions of graphs with many three-paths

This page was built for publication: Caterpillars are antimagic

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