期刊名称：AKCE International Journal of Graphs and Combinatorics
印刷版ISSN：0972-8600
出版年度：2016
卷号：13
期号：1
页码：54-64
DOI：10.1016/j.akcej.2016.02.007
语种：English
出版社：Elsevier
摘要：Abstract The square of a graph G = ( V , E ) , denoted by G 2 , is a graph on the same vertex set V ( G ) such that two vertices x and y are adjacent in G 2 if and only if there is a path of length one or two between x and y in G . In this article, a new linear time algorithm is presented to compute G 2 from G when G is an interval graph. Also a linear time algorithm is designed to find all the maximal cliques of G 2 from G . Application of square of interval graphs in the field of L ( h , k ) -labelling problem is also discussed. Finally, it is shown that L ( 1 , 1 ) -labelling number of an interval graph can be computed in linear time.
关键词：KeywordsenInterval graphSquare of graphClique L ( 1 , 1 ) -labelling
