Let d(G) denote the minimum degree of a Graph G. Naik, Rao, Shrikhande and Singhi proved the surprising result in [1, 7, 8] that there exists a finite family of forbidden graphs for characterizing graphs of the family L<sup>k</sup><sub>1</sub> for k=3 with d(gG) > 68 . In [4], Jacobson et al. improved the d(G) to 19 and gave a polynomial algorithm to decide whether a graph is a L<sup>k</sup><sub>1</sub> for k=3. The algorithm follows from a simple recursive characterization of L<sup>k</sup><sub>1</sub> and relies on the fact that there is a polynomial time recognition algorithm for members of L<sup>2</sup><sub>1</sub>. Jacboson et al. could not extend finite forbidden subgraph characterization proved in [7] for d(G) > 68 to 19.
The complexity of recognizing members of L<sup>k</sup><sub>1</sub> without any minimum degree (edge degree) constraint is not known.
In [1,7,8], Naik etl al. obtained parallel results for any k > 2 under the additional condition that k<sup>3</sup> -2k<sup>2</sup> + 1 is a lower bound on the 'edge-degree of the graph. Define the edge-degree d<sub>e</sub> (G) of the edge uv in G as the sum of the degrees of the vertices u and v in G. Both the results in [7, 8] imply polynomial recognition algorithms for graphs under the corresponding minimum degree and minimum edge-degree conditions. Essentially in [4], Jacobson et al. extended the same method to yield a polynomial recognition algorithm for L<sup>k</sup><sub>1</sub>, k > 2, provided the minimum edge-degree of the graphs is at least 2k<sup>2</sup>-3k+1. Actually this is an improvement on the cubic bound that follows from the corresponding finite characterization result in [7].
In [6], Metelsky and Tyshkevich, gave the finite forbidden subgraph characterization for L<sup>k</sup><sub>1</sub>, k=3 with d(gG) at least 19 analogous to [7]. Metelsky etl al. characterized Line graphs of Graphs with d(gG) > 4 in terms of fewer number of forbidden induced subgraphs from the set of nine Beineke graphs. Furthermore, they also proved that for k > 3 and an arbitrary constant c, L<sup>k</sup><sub>1</sub> with d(G) > c) cannot be characterized by a finite list of forbidden induced subgraphs.
In [10,], Zverovivh proved that for k > 2, there exists a finite family of forbidden graphs for characterizing the graphs with minimum edge-degree condition stated in [6] for L<sup>k</sup><sub>1</sub>.
