- and -labeling problems on interval graphs

Abstract

For a given graph , the - and -labeling problems assign the labels to the vertices of . Let be the set of non-negative integers. An - and -labeling of a graph is a function such that , for respectively, where represents the distance (minimum number of edges) between the vertices and , and . The - and -labeling numbers of a graph , are denoted by and and they are the difference between highest and lowest labels used in - and -labeling respectively. In this paper, for an interval graph , it is shown that and , where represents the maximum degree of the vertices of . Also, two algorithms are designed to label an interval graph by maintaining - and -labeling conditions. The time complexities of both the algorithms are , where represent the number of vertices of .

Keywords

• frequency assignment
• -labeling
• -labeling
• interval graphs