Line graph of a hypergraph: Difference between revisions

Revision as of 15:49, 12 April 2008

Revision as of 17:58, 12 April 2008

Line 7:

==Line graphs of ''k''-uniform hypergraphs, ''k'' ≥ 3==

Beineke (1968) characterized line graphs of graphs by a list of 9 forbidden induced subgraphs (See the article on [[line graph]]s.). No characterization by forbidden induced subgraphs is known of line graphs of k-uniform hypergraphs for any k ≥ 3, and Lóvász (1977) showed there is no such characterization by a finite list if k = 3.

Krausz (1943) characterized line graphs of graphs in terms of [[clique]] covers (See the article on line graphs.).

Krausz (1943) characterized line graphs of graphs in terms of [[clique]] covers (See the article on line graphs.). A global characterization of Krausz type for the line graphs of k-uniform hypergraphs for any k ≥ 3 was given by Berge (1989).

==Line graphs of ''k''-uniform linear hypergraphs, ''k'' ≥ 3==

Line 19 ⟶ 18:

The difficulty in finding a characterization of linear k-uniform hypergraphs is due to the fact that there are infinitely many forbidden induced subgraphs. To give examples, for m > 0, consider a chain of m diamond graphs such that the consecutive diamonds share vertices of degree two. For k ≥ 3, add pendant edges at every vertex of degree 2 or 4 to get one of the families of minimal forbidden subgraphs in Naik et al. (1980, 1982), as shown here. This does not rule out either the existence of a polynomial recognition or the possibility of a forbidden induced subgraph characterization similar to Beineke's of line graphs of graphs.

[[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 (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. TheMinimum edge degree lowerat boundleast was a cubic polynomialk³-2k²+1 fromin Naik et al., which is improvedreduced to a polynomial of degree 2k²-3k+1 byin Jacobson et al. (1997) and Zverovich (2004) to characterize the line graphs of k-uniform linear hyper graphshypergraphs 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.