Antimagic labelings of caterpillars

DOI10.1016/J.AMC.2018.11.043zbMATH Open1428.05274arXiv1708.00624OpenAlexW2744449504MaRDI QIDQ2008558FDOQ2008558

Authors: Antoni Lozano, Mercè Mora, Carlos Seara 

Publication date: 26 November 2019

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

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.

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

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

zbMATH Keywords

algorithmsantimagic graphslabelings

Mathematics Subject Classification ID

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

Cites Work

• On zero-sum partitions and anti-magic trees
• Antimagic labelling of vertex weighted graphs
• Combinatorial Nullstellensatz
• Lattice grids and prisms are antimagic
• Dense graphs are antimagic
• Weighted antimagic labeling: an algorithmic approach
• Regular bipartite graphs are antimagic
• Title not available (Why is that?)
• 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
• Antimagic Labeling of Regular Graphs
• Anti-magic labeling of trees
• Title not available (Why is that?)
• A new class of antimagic Cartesian product graphs
• Approximate results for rainbow labelings
• Graphs of large linear size are antimagic
• Regular Graphs of Odd Degree Are Antimagic
• Antimagic labeling of generalized pyramid graphs

Cited In (17)

• Title not available (Why is that?)
• 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
• Antimagic labeling of forests with sets of consecutive integers
• Antimagic orientation of lobsters
• Caterpillars are antimagic
• Antimagic orientations for the complete \(k\)-ary trees
• 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
• Shifted-antimagic labelings for graphs
• A lower bound and several exact results on the \(d\)-lucky number
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)