Content deleted Content added
Tangi-tamma (talk | contribs) mNo edit summary |
Tangi-tamma (talk | contribs) mNo edit summary |
||
Line 8:
The complexity of recognizing members of L<sup>k</sup><sub>1</sub> without any minimum degree (Edge degree) constraint is not known.
In [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(g) at least 19 analogous to [7]. Metelsky etl al. characterized Line graphs of Graphs with d(g) > 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-1) cannot be characterized by a finite list of forbidden induced subgraphs.
| |||