A study on maximum cardinality r-L(2, 1)-labelling problem on circular-arc graph and its application

Abstract

Graph labelling is one of the most applicable problem in graph theory, often applied to solve real-world challenges. This article explores a range of L(2, 1)-labelling problems (L21LPs), specifically focusing on the r-L21LP within CirGs. In the standard L21LP, each vertex in a graph is assigned a label from a set of non-negative integers. The labeling follows these rules: for adjacent vertices, the label difference must be at least 2; for vertices at distance two, the label difference must be at least 1; and for vertices farther apart, there are no label restrictions. The difference between the highest and lowest labels among all vertices is denoted as λ2,1(G). This paper introduces a variation of the L(2, 1)-labelling problem, known as the restricted L21LP, where a maximum label limit r is imposed. Consequently, the valid labels are restricted to {0, 1, 2, . . . , r}. The objective is to L(2, 1)-label the vertices of G using these limited labels to maximize the number of labelled vertices. If the available r labels suffice to label all vertices, then every vertex is labelled; otherwise, some vertices remain unlabelled. A polynomial-time algorithm is proposed to address this problem, along with illustrative examples. Additionally, an application scenario is presented, demonstrating the use of this labelling scheme to allocate program slots on telecasting channels for advertising products or disseminating information for organizations.