Line graph of a hypergraph: Difference between revisions

Revision as of 15:42, 12 April 2008

Revision as of 15:49, 12 April 2008

Line 21:

[[Image:Repeated_diamond_graph.svg | 350px]]

There are some interesting characterizations available for line graphs of linear k-uniform hypergraphs due to various authors (Naik et al. 1980, 1982, Jacobson et al. 1997, Metelsky et al. 1997, and Zverovich 2004.) under constraints on the minimum degree or the minimum edge degree of G. The edge degree lower bound was a cubic polynomial from Naik et al., which is improved to a polynomial of degree 2 by Metelsky et al. (1997), Jacobson et al. (1997) and Zverovich (2004) to characterize the line graphs of k-uniform linear hyper graphs 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 (Metelsky et al. 1997 and Jacobson et al. 1997). Skums et al. (2005) reduced the minimum degree to 10.