Shifted-antimagic labelings for graphs

DOI10.1007/S00373-021-02305-WMaRDI QIDQ2045398zbMATH OpenOpenAlexFDO

Authors Fei-Huang Chang, Wei-Tian Li, Zhishi Pan, Hongbin Chen

Publication date 12 August 2021

Published in Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

antimagic labelingdisconnected graphstrees

Mathematics Subject Classification ID

Trees (05C05) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: The concept of antimagic labelings of a graph is to produce distinct vertex sums by labeling edges through consecutive numbers starting from one. A long-standing conjecture is that every connected graph, except a single edge, is antimagic. Some graphs are known to be antimagic, but little has been known about sparse graphs, not even trees. This paper studies a weak version called $k$-shifted-antimagic labelings which allow the consecutive numbers starting from $k+1$, instead of starting from 1, where $k$ can be any integer. This paper establishes connections among various concepts proposed in the literature of antimagic labelings and extends previous results in three aspects: $$ Some classes of graphs, including trees and graphs whose vertices are of odd degrees, which have not been verified to be antimagic are shown to be $k$-shifted-antimagic for sufficiently large $k$. $$ Some graphs are proved $k$-shifted-antimagic for all $k$, while some are proved not for some particular $k$. $$ Disconnected graphs are also considered.

Review text

An antimagic labeling of a finite simple undirected graph with $q$ edges is a bijection from the set of edges to the set of integers $\{1, 2 , \dots, q\}$ such that the vertex sums are pairwise distinct, where the vertex sum at vertex $u$ is the sum of labels of all edges incident to such a vertex and this concept is well studied in the literature. This paper studies a weak version called $k$-shifted-antimagic labeling which allows the consecutive numbers starting from $k+1$, instead of $1$, where $k$ is any positive integer. This paper establishes connections among various concepts proposed in the literature on antimagic labelings. Let $G=(V,E)$ be a graph with $|E(G)| = m$. For a given positive integer $k$ if there exists an injective function $f$ from $E(G)$ to $\{k+1, k+2, \dots, k+m\}$ such that the vertex sums $s(v)$ for all the vertices $v$ of $G$ are distinct then we say that $G$ admits $k$-shifted-antimagic labeling. If $G$ admits such a labeling then $G$ is called the $k$-shifted-antimagic graph. In this paper, the authors analyse the values of $k$ for a given graph $G$ such that $G$ is $k$-shifted-antimagic graph. The study on disconnected graphs for being antimagic or not has received very little attention in the literature. The authors of this paper show some classes of disconnected graphs which are $k$-shifted-antimagic or not $k$-shifted-antimagic for some values of $k$. In this paper, the disconnected graph $G$ having three component, say $G_1$, $G_2$ and $G_3$ is denoted by $G := G_1+G_2+G_3$ and ``+ is taken as the disjoint union of graphs. This paper opens a new study in the field of graph labeling.

Recommendations

• Antimagic labeling of forests with sets of consecutive integers
• Labeling trees of small diameters with consecutive integers
• Antimagic labeling of new classes of trees
• On antimagic labeling of odd regular graphs
• Sparse graphs with vertex antimagic edge labelings

Cites work

• Anti-magic labeling of trees
• Antimagic labeling of cubic graphs
• Antimagic labeling of regular graphs
• Antimagic labelings of caterpillars
• Antimagic labelling of vertex weighted graphs
• Anti‐magic graphs via the Combinatorial NullStellenSatz
• Computing and Combinatorics
• Dense graphs are antimagic
• scientific article; zbMATH DE number 6712556 (Why is no real title available?)
• scientific article; zbMATH DE number 6537750 (Why is no real title available?)
• scientific article; zbMATH DE number 728185 (Why is no real title available?)
• On anti-magic labeling for graph products
• On antimagic labeling for power of cycles.
• On the antimagic labeling of star forests
• On zero-sum partitions and anti-magic trees
• Regular bipartite graphs are antimagic
• Regular graphs of odd degree are antimagic
• The strongly antimagic labelings of double spiders

Cited in

(8)

• Antimagic labeling of forests with sets of consecutive integers
• Antimagic labeling for unions of graphs with many three-paths
• Labeling trees of small diameters with consecutive integers
• Graph antimagic labeling: a survey
• Every graph is homeomorphic to an antimagic bipartite graph
• On \(k\)-shifted antimagic spider forests
• Antimagic labeling for subdivisions of graphs
• Constructing the antimagic labelings for double stars union paths on three vertices

This page was built for publication: Shifted-antimagic labelings for graphs

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