The line completion number of hypercubes

Abstract

In 1992, Bagga, Beineke, and Varma introduced the concept of the super line graph of index r of a graph G, denoted by ℒr(G). The vertices of ℒr(G)are the r-subsets of E(G), and two vertices S and T are adjacent if there exist s∈S and t∈T such that s and t are adjacent edges in G. They also defined the line completion number lc(G)of graph G to be the minimum index r for which ℒr(G)is complete. They found the line completion number for certain classes of graphs. In this paper, we find the line completion number of hypercube Qnfor every n. Keywords: Super line graph, Line completion number, Induced subgraph, Hypercube