L(h,k)-Labeling of Intersection Graphs

L(h,k)-Labeling of Intersection Graphs

Sk. Amanathulla, Madhumangal Pal
Copyright: © 2020 |Pages: 36
DOI: 10.4018/978-1-5225-9380-5.ch007
OnDemand:
(Individual Chapters)
Available
$37.50
Current Special Offers
No Current Special Offers
TOTAL SAVINGS: $37.50

Abstract

One important problem in graph theory is graph coloring or graph labeling. Labeling problem is a well-studied problem due to its wide applications, especially in frequency assignment in (mobile) communication system, coding theory, ray crystallography, radar, circuit design, etc. For two non-negative integers, labeling of a graph is a function from the node set to the set of non-negative integers such that if and if, where it represents the distance between the nodes. Intersection graph is a very important subclass of graph. Unit disc graph, chordal graph, interval graph, circular-arc graph, permutation graph, trapezoid graph, etc. are the important subclasses of intersection graphs. In this chapter, the authors discuss labeling for intersection graphs, specially for interval graphs, circular-arc graphs, permutation graphs, trapezoid graphs, etc., and have presented a lot of results for this problem.
Chapter Preview
Top

Basic Concept Of L(H,K)-Labeling

In this section, the definition and span of L(h,k)-labeling is presented. Different variations of L(h,k)-labeling is also highlighted in this section. The definition of L(h,k)-labeling is as follows.

Definition 1 L(h,k)-labeling: Given a graph 978-1-5225-9380-5.ch007.m13 and two nonnegative integers 978-1-5225-9380-5.ch007.m14 and 978-1-5225-9380-5.ch007.m15, an L(h,k)-labeling is an assignment of non-negative integers to the nodes of 978-1-5225-9380-5.ch007.m16 such that adjacent nodes are labelled using colours at least 978-1-5225-9380-5.ch007.m17 apart, and nodes having a common neighbour are labelled using colours at least 978-1-5225-9380-5.ch007.m18 apart. The difference between largest and smallest labels is called the span. The aim of the 978-1-5225-9380-5.ch007.m19-labeling problem is to minimize the span. The minimum span over all possible labeling functions is denoted by 978-1-5225-9380-5.ch007.m20 and is called 978-1-5225-9380-5.ch007.m21-number of 978-1-5225-9380-5.ch007.m22.

Complete Chapter List

Search this Book:
Reset