Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4646518 | AKCE International Journal of Graphs and Combinatorics | 2016 | 11 Pages |
Abstract
The square of a graph G=(V,E)G=(V,E), denoted by G2G2, is a graph on the same vertex set V(G)V(G) such that two vertices xx and yy are adjacent in G2G2 if and only if there is a path of length one or two between xx and yy in GG. In this article, a new linear time algorithm is presented to compute G2G2 from GG when GG is an interval graph. Also a linear time algorithm is designed to find all the maximal cliques of G2G2 from GG. Application of square of interval graphs in the field of L(h,k)L(h,k)-labelling problem is also discussed. Finally, it is shown that L(1,1)L(1,1)-labelling number of an interval graph can be computed in linear time.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Satyabrata Paul, Madhumangal Pal, Anita Pal,