Revision as of 01:47, 12 March 2008 edit Tangi-tamma (talk \| contribs) 1,091 edits →Intersection (Line) graphs of k-uniform linear Hypergraph ← Previous edit		Revision as of 01:53, 12 March 2008 edit undo Tangi-tamma (talk \| contribs) 1,091 edits →Intersection (Line) graphs of k-uniform linear Hypergraph Next edit →
Line 9: The complexity of recognizing members of L<sup>k</sup><sub>1</sub> without any minimum degree constraint is not known. In [7], Rao 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>ve</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] imply polynomial recognition algorithms for graphs under the corresponding minimum degree and minimum edge-degree conditions. Essentially they they 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) at least 5 in terms of fewer number of forbidden induced subgraph 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) at least c cannot be characterized by a finite list of forbidden induced subgraphs.

Line graph of a hypergraph: Difference between revisions