A number theoretic problem on super line graphs. Issue 2 (1st August 2016)

• Record Type: Journal Article
• Authors: Bagga, Jay; Beineke, Lowell; Varma, Badri
• Is Part Of: AKCE International Journal of Graphs and Combinatorics. Volume 13:Issue 2(2016)
• Page Start: 177
• Page End: 190
• Publication Date: 2016-08-01
• Subjects: Line graph -- Super line graph -- Line completion number
• DOI: 10.1016/j.akcej.2016.05.001
• Languages: English
• ISSNs: 0972-8600

Abstract

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, L r ( 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 L r ( G ) is complete. In this paper we investigate the line completion number of K m, 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 ( K m, 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 ( K m, 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.