Antimagic labelings of caterpillars

DOI10.1016/J.AMC.2018.11.043MaRDI QIDQ2008558zbMATH OpenOpenAlexFDO

Authors Antoni Lozano, Mercè Mora, Carlos Seara

Publication date 26 November 2019

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.00624, http://hdl.handle.net/2117/125781

zbMATH Keywords

algorithmsantimagic graphslabelings

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: A $k$-antimagic labeling of a graph $G$ is an injection from $E(G)$ to $1,2,dots,|E(G)|+k$ 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$. We call a graph $k$-antimagic when it has a $k$-antimagic labeling, and antimagic when it is 0-antimagic. Hartsfield and Ringel conjectured that every simple connected graph other than $K_2$ is antimagic, but the conjecture is still open even for trees. Here we study $k$-antimagic labelings of caterpillars, which are defined as trees the removal of whose leaves produces a path, called its spine. As a general result, we use constructive techniques to prove that any caterpillar of order $n$ is $(lfloor(n-1)/2floor-2)$-antimagic. Furthermore, if $C$ is a caterpillar with a spine of order $s$, we prove that when $C$ has at least $lfloor(3s+1)/2floor$ leaves or $lfloor(s-1)/2floor$ consecutive vertices of degree at most 2 at one end of a longest path, then $C$ is antimagic. As a consequence of a result by Wong and Zhu, we also prove that if $p$ is a prime number, any caterpillar with a spine of order $p$, $p-1$ or $p-2$ is $1$-antimagic.

Recommendations

• Product antimagic labeling of caterpillars
• Caterpillars have antimagic orientations
• Caterpillars are antimagic
• Antimagic orientation of subdivided caterpillars
• Anti-magic labeling of trees
• Caterpillars with maximum degree 3 are antimagic
• Weighted antimagic labeling
• scientific article; zbMATH DE number 2186481
• Antimagic labelings of antiprisms

Cites work

• scientific article; zbMATH DE number 47933 (Why is no real title available?)
• scientific article; zbMATH DE number 1944626 (Why is no real title available?)
• A new class of antimagic Cartesian product graphs
• Anti-magic labeling of trees
• Antimagic labeling of cubic graphs
• Antimagic labeling of generalized pyramid graphs
• Antimagic labeling of regular graphs
• Antimagic labelling of vertex weighted graphs
• Antimagic properties of graphs with large maximum degree
• Anti‐magic graphs via the Combinatorial NullStellenSatz
• Approximate results for rainbow labelings
• Combinatorial Nullstellensatz
• Computing and Combinatorics
• Dense graphs are antimagic
• Graphs of large linear size are antimagic
• Lattice grids and prisms are antimagic
• On anti-magic labeling for graph products
• On zero-sum partitions and anti-magic trees
• Regular bipartite graphs are antimagic
• Regular graphs of odd degree are antimagic
• The antimagicness of the Cartesian product of graphs
• Weighted antimagic labeling: an algorithmic approach

Cited in

(19)

• scientific article; zbMATH DE number 5844281 (Why is no real title available?)
• Every graph is homeomorphic to an antimagic bipartite graph
• Perfectly antimagic total labeling of star-like trees and the corona product of two graphs
• Caterpillars with maximum degree 3 are antimagic
• Caterpillars have antimagic orientations
• Product antimagic labeling of caterpillars
• Antimagic labeling of forests with sets of consecutive integers
• Antimagic orientation of lobsters
• Caterpillars are antimagic
• Antimagic orientations for the complete \(k\)-ary trees
• Antimagic labeling of some biregular bipartite graphs
• On \(k\)-shifted antimagic spider forests
• List-antimagic labeling of vertex-weighted graphs
• Trees whose even-degree vertices induce a path are antimagic
• Shifted-antimagic labelings for graphs
• A lower bound and several exact results on the \(d\)-lucky number
• scientific article; zbMATH DE number 6537750 (Why is no real title available?)
• scientific article; zbMATH DE number 2186481 (Why is no real title available?)
• Antimagic labeling for unions of graphs with many three-paths

This page was built for publication: Antimagic labelings of caterpillars

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