A number theoretic problem on super line graphs
Jay S. Bagga, Lowell W. Beineke, Badri N. Varma · AKCE International Journal of Graphs and Combinatorics · 2016
In Bagga et al. (1995) a generalization of the line graph concept was introduced. Given a graph with at least edges, the super line graph of index , , has as its vertices the sets of edges of , with two adjacent if there is an edge in one set adjacent to an edge in the other set. The line completion number of a graph is the least index for which is complete. In this paper we investigate the line completion number of . This turns out to be an interesting optimization problem in number theory, with results depending on the parities of and . If and is a fixed even number, then has been found for all even values of and for all but finitely many odd values. However, when is odd, the exact value of 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.