Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8902754 | AKCE International Journal of Graphs and Combinatorics | 2017 | 11 Pages |
Abstract
For a given graph G=(V,E), the L(3,2,1)- and L(4,3,2,1)-labeling problems assign the labels to the vertices of G. Let Zâ be the set of non-negative integers. An L(3,2,1)- and L(4,3,2,1)-labeling of a graph G is a function f:VâZâ such that |f(x)âf(y)|â¥kâd(x,y), for k=4,5 respectively, where d(x,y) represents the distance (minimum number of edges) between the vertices x and y, and 1â¤d(x,y)â¤kâ1. The L(3,2,1)- and L(4,3,2,1)-labeling numbers of a graph G, are denoted by λ3,2,1(G) and λ4,3,2,1(G) and they are the difference between highest and lowest labels used in L(3,2,1)- and L(4,3,2,1)-labeling respectively. In this paper, for an interval graph G, it is shown that λ3,2,1(G)â¤6Îâ3 and λ4,3,2,1(G)â¤10Îâ6, where Î represents the maximum degree of the vertices of G. Also, two algorithms are designed to label an interval graph by maintaining L(3,2,1)- and L(4,3,2,1)-labeling conditions. The time complexities of both the algorithms are O(nÎ2), where n represent the number of vertices of G.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Sk Amanathulla, Madhumangal Pal,