Revision as of 06:36, 14 April 2008 edit Zaslav (talk \| contribs) Extended confirmed users 15,699 edits Rm cleanup tag. Article is much better. ← Previous edit		Revision as of 22:29, 14 April 2008 edit undo Tangi-tamma (talk \| contribs) 1,091 edits m →Also add the year Next edit →
Line 20: [[Image:Repeated diamond graph.svg\|350px\|center]] There are some interesting characterizations available for line graphs of linear ''k''-uniform hypergraphs due to various authors ({{harvs\|last1 = Naik\|last2 = Rao\|last3 = Shrikhande\|last4 = Singhi\|year = 1980\|year2 = 1982\|nb = yes}}, {{harvnb\|Jacobson\|Kézdy\|Lehel\|1997}}, {{harvnb\|Metelsky\|Tyshkevich\|1997}}, and {{harvnb\|Zverovich\|2004}}) under constraints on the minimum degree or the minimum edge degree of G. Minimum edge degree at least ''k''<sup>3</sup>-2''k''<sup>2</sup>+1 in {{harvtxt\|Naik ~~et al.~~\|Rao\|Shrikhande\|Singhi\|1980}} is reduced to 2''k''<sup>2</sup>-3''k''+1 in {{harvtxt\|Jacobson\|Kézdy\|Lehel\|1997}} and {{harvtxt\|Zverovich\|2004}} to characterize line graphs of ''k''-uniform linear hypergraphs for any ''k'' ≥ 3. The complexity of recognizing line graphs of linear ''k''-uniform hypergraphs without any constraint on minimum degree (or minimum edge-degree) is not known. For ''k'' = 3 and minimum degree at least 19, recognition is possible in polynomial time ({{harvnb\|Jacobson\|Kézdy\|Lehel\|1997}} and {{harvnb\|Metelsky\|Tyshkevich\|1997}}). {{harvtxt\|Skums\|Suzdal'\|Tyshkevich\|2005}} reduced the minimum degree to 10.

Line graph of a hypergraph: Difference between revisions