Anti-k-labeling of graphs

DOI10.1016/J.AMC.2019.06.063MaRDI QIDQ2286097zbMATH OpenOpenAlexWikidataFDO

Authors Xiaxia Guan, Shurong Zhang, Lin Chen, Weihua Yang, Ronghua Li

Publication date 9 January 2020

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

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

zbMATH Keywords

channel assignment problem

Mathematics Subject Classification ID

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

Abstract: It is well known that the labeling problems of graphs arise in many (but not limited to) networking and telecommunication contexts. In this paper we introduce the anti-$k$-labeling problem of graphs which we seek to minimize the similarity (or distance) of neighboring nodes. For example, in the fundamental frequency assignment problem in wireless networks where each node is assigned a frequency, it is usually desirable to limit or minimize the frequency gap between neighboring nodes so as to limit interference. Let $kgeq1$ be an integer and $psi$ is a labeling function (anti-$k$-labeling) from $V(G)$ to $1,2,cdots,k$ for a graph $G$. A {em no-hole anti-$k$-labeling} is an anti-$k$-labeling using all labels between 1 and $k$. We define $w_{psi}(e)=|psi(u)-psi(v)|$ for an edge $e=uv$ and $w_{psi}(G)=min{w}_{psi}(e):einE(G)$ for an anti-$k$-labeling $psi$ of the graph $G$. {em The anti-$k$-labeling number} of a graph $G$, $m{c}_k(G)$ is $max{w}_{psi}(G):psi$. In this paper, we first show that $m{c}_k(G)=lfloorfrack-1chi-1floor$, and the problem that determines $m{c}_k(G)$ of graphs is NP-hard. We mainly obtain the lower bounds on no-hole anti-$n$-labeling number for trees, grids and $n$-cubes.

Recommendations

• No-hole -L(k,k-1,,2,1)-labeling for square grid
• Radio k-labelings for Cartesian products of graphs
• Structural Information and Communication Complexity
• Disproofs of two conjectures on no hole anti-n-labeling of graphs
• Optimal \(L(h,k)\)-labeling of regular grids

Cites work

• A survey on labeling graphs with a condition at distance two
• Distance-two labelings of digraphs
• Graph theory with applications
• scientific article; zbMATH DE number 3853101 (Why is no real title available?)
• scientific article; zbMATH DE number 2197903 (Why is no real title available?)
• Labelling Graphs with a Condition at Distance 2
• No-hole (r+1)-distant colorings
• On the \(L(p,1)\)-labelling of graphs

Cited in

(4)

• Disproofs of two conjectures on no hole anti-n-labeling of graphs
• Incidence coloring of mycielskians with fast algorithm
• No-hole -L(k,k-1,,2,1)-labeling for square grid
• Structural Information and Communication Complexity

This page was built for publication: Anti-\(k\)-labeling of graphs

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