Revision as of 00:43, 11 March 2008 edit Tangi-tamma (talk \| contribs) 1,091 edits m →Linear Intersection (Line) graphs of k-uniform Hypergraph ← Previous edit		Revision as of 00:52, 11 March 2008 edit undo Tangi-tamma (talk \| contribs) 1,091 edits m →Linear Intersection (Line) graphs of k-uniform Hypergraph Next edit →
Line 10: 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 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 garphs under the corresponding minimum degree and minimum edge-degree conditions. In [6] Metelsky and Tyshkevich, gave the finite forbidden subgraph characterization for linear 3-uniform hypergraphs with minimum degree at least 19 in G analogous to [7]. Metelsky etl al. ~~in [6]~~ characterized Line graphs of Graphs with minimum degree condition with minimum degree 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, the set of all Intersection graphs of k-uniform linear hypergraphs with minium degree at least c cannot be characterized by a finite list of forbidden induced subgraphs. In progress...

Line graph of a hypergraph: Difference between revisions