Line graph of a hypergraph

You must add a |reason= parameter to this Cleanup template – replace it with {{Cleanup|reason=<Fill reason here>}}, or remove the Cleanup template.
In mathematics, a hypergraph is a generalization of a graph, where edges can contain any finite number of vertices, and the line graph of a hypergraph is a generalization of the line graph of a graph. The precise definition is that the line graph of a hypergraph is the graph whose vertex set is the set of edges of the hypergraph, with two edges adjacent when they have nonempty intersection. Thus, the line graph of a hypergraph is the same as the intersection graph of a family of finite sets.

However, the questions asked tend to be different. Questions about line graphs of hypergraphs are often generalizations of questions about line graphs of graphs. For instance, a hypergraph whose edges all have size k is called k -uniform. (A 2-uniform hypergraph is a graph.). In hypergraph theory, it is often natural to require that hypergraphs be k-uniform. Every graph is the line graph of some hypergraph, but, given a fixed edge size k, not every graph is a line graph of some k-uniform hypergraph. A main problem is to characterize those that are, for each k ≥ 3.

A hypergraph is linear if each pair of hyperedges intersects in at most one vertex. Every graph is the line graph, not only of some hypergraph, but of some linear hypergraph (Berge 1989).

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 graphs.) 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.) 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

A global characterization of Krausz type for the line graphs of k-uniform linear hypergraphs for any k ≥ 3 was given by Naik et al. (1980).

Naik et al. (1980) found a finite list of forbidden induced subgraphs for linear 3-uniform hypergraphs with minimum vertex degree at least 69. Metelsky et al. (1997) and Jacobson et al.(1997) improved this bound to 19. Metelsky et al. (1997) also proved that, if k > 3, no such finite list exists for linear k-uniform hypergraphs, no matter what lower bound is placed on the degree.

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.

 

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. Minimum edge degree at least k³-2k²+1 in Naik et al. is reduced to 2k²-3k+1 in Jacobson et al. (1997) and 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 (Metelsky et al. 1997 and Jacobson et al. 1997). Skums et al. (2005) reduced the minimum degree to 10.

There are many interesting open problems and conjectures in Naik et al., Jacoboson et al., Metelsky et al. and Zverovich.

References

• L. W. Beineke (1968), On derived graphs and digraphs. In: Beitrage zur Graphentheorie [H. Saks et al., eds.], Teubner, Leipzig, pp. 17-23.

• C. Berge, 1989, Hypergraphs: Combinatorics of Finite Sets. Amsterdam: North-Holland.

• J.C. Bermond, M.C. Heydemann, and D. Sotteau (1977), Line graphs of hypergraphs I. Discrete Mathematics, vol. 18, pp. 235-241.

• M. C. Heydemann and D. Scotteau (1976), Line graphs of hypergraphs II. In Colloq. Math. Soc. J. Bolyai, vol. 18, pp. 567-582

• J. Krausz (1943), Demonstration nouvelle d'un theorem de Whitney sur les reseaux. Mat. Fiz. Lapok, vol. 50, pp. 75-89

• L. Lóvász. Problem 9. in: Beitrage zur Graphentheorie und deren Ansendungen. Vortgetragen auf dem international Colloquium in Oberhof (DDR) (1977), p. 313.

• M S. Jacobson, Andre E. Kezdy, and Jeno Lehel (1997), Recognizing Intersection Graphs of Linear Uniform Hypergraphs. Graphs and Combinatorics, vol. 13, pp. 359-367.

• Yury Metelsky and Regina Tyshkevich (1997), On line graphs of linear 3-uniform hypergraphs. J. of Graph Theory, vol. 25, pp. 243-251.

• R. N. Naik, S. B. Rao, S. S. Shrikhande, and N. M. Singhi (1980), Intersection graphs of k-uniform hypergraphs. Annals of Discrete Mathematics, vol. 6, pp. 275-279.

• R. N. Naik, S. B. Rao, S. S. Shrikhande, and N. M. Singhi (1982), Intersection graphs of k-uniform linear hypergraphs. European J. Combinatorics, vol. 3, pp. 159-172.

• P.V. Skums, S.V. Suzdal and R.I. Tyshkevich, Edge intersection of linear 3-unform hypergraphs, Mechanics and Mathematics faculty, Belarus State University, Minsk, Belarus – October 2005

• Igor E. Zverovich (2004), A solution to a problem of Jacobson, Kezdy and Lethel, DIMACS Publications. pp. 1-7.