Content deleted Content added
Tangi-tamma (talk | contribs) |
Tangi-tamma (talk | contribs) |
||
Line 17:
<!-- Deleted image removed: [[Image:Hypergraph2.jpeg ]] -->
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(G) > 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 d(G) > 19.
The complexity of recognizing members of L<sup>k</sup><sub>1</sub> without any minimum degree (edge degree) constraint is not known.
| |||