Line completion number of grid graph Pn × Pm

Document Type : Original paper


Christ University



The concept of super line graph was introduced in the year 1995 by Bagga, Beineke and Varma. Given a graph with at least r edges, the super line graph of index r, Lr(G), has as its vertices the sets of r-edges of G, with two adjacent if there is an edge in one set adjacent to an edge in the other set. The line completion number lc(G) of a graph G is the least positive integer r for which Lr(G) is a complete graph. In this paper, we find the line completion number of grid graph Pn × Pm for various cases of n and m.


Main Subjects