A number theoretic problem on super line graphs

Abstract

In Bagga et al. (1995) a generalization of the line graph concept was introduced. Given a graph G 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 index r for which Lr(G) is complete. In this paper we investigate the line completion number of Km,n. This turns out to be an interesting optimization problem in number theory, with results depending on the parities of m and n. If m≤n and m is a fixed even number, then lc(Km,n) has been found for all even values of n and for all but finitely many odd values. However, when m is odd, the exact value of lc(Km,n) has been found in relatively few cases, and the main results concern lower bounds for the parameter. Thus, the general problem is still open, with about half of the cases unsettled.

Keywords

• Line graph
• Super line graph
• Line completion number