A note on (s, t)-relaxed L(2, 1)-labeling of graphs

A note on (s, t)-relaxed L(2, 1)-labeling of graphs

0.00 Avg rating0 Votes
Article ID: iaor20172796
Volume: 34
Issue: 2
Start Page Number: 378
End Page Number: 382
Publication Date: Aug 2017
Journal: Journal of Combinatorial Optimization
Authors: ,
Keywords: combinatorial optimization, graphs, heuristics
Abstract:

Let G = ( V , E ) equ1 be a graph. For two vertices u and v in G, we denote d G ( u , v ) equ2 the distance between u and v. A vertex v is called an i‐neighbor of u if d G ( u , v ) = i equ3 . Let s, t and k be nonnegative integers. An (s, t)‐relaxed kL(2, 1)‐labeling of a graph G is an assignment of labels from { 0 , 1 , , k } equ4 to the vertices of G if the following three conditions are met: (1) adjacent vertices get different labels; (2) for any vertex u of G, there are at most s 1‐neighbors of u receiving labels from { f ( u ) 1 , f ( u ) + 1 } equ5 ; (3) for any vertex u of G, the number of 2‐neighbors of u assigned the label f(u) is at most t. The (s, t)‐relaxed L(2, 1)‐labeling number λ 2 , 1 s , t ( G ) equ6 of G is the minimum k such that G admits an (s, t)‐relaxed kL(2, 1)‐labeling. In this article, we refute Conjecture 4 and Conjecture 5 stated in (Lin in J Comb Optim. doi: 10.1007/s10878‐014‐9746-9, 2013).

Reviews

Required fields are marked *. Your email address will not be published.