Line graphs of hypergraphs

From Wikiversity

This article may provide insufficient context for those unfamiliar with the subject. Please discuss this issue on the talk page, and/or replace this tag with a more specific message. Editing help is available.

Template:Dated prod

[edit] Introduction

Let L²₁ stand for the family of Line graphs of graphs. The characterization of L²₁ the Line graphs was solved by Van Rooij and Wilf [7] and by Beineke [1]. A characterization of L²₁ in terms of Clique covers is given by J. Krausz [6]. Rooij and Wilf used the notion of even and odd triangles to characterize line graphs.

In mathematics, a hypergraph is a generalization of a graph, where edges can contain any number of vertices. A hypergraph is linear if any two edges have at most one common vertex. A k-uniform hypergraph is a hypegraph with edges of size k. A k-uniform linear hypergraph is a k-uniform hypergrah that is linear, where k 2. Obviously, graphs are 2-uniform linear hypergraphs.

[edit] Line graphs of k-uniform linear hypergraphs , k 3

The concept of line graphs generalizes to hypergraphs by various authors in [2,3,4,8]. Let L^k₁ stand for the family of line graphs of k-uniform linear hypergraphs. The complexity of recognizing members of L^k₁ without any minimum degree (or edge degree) constraint is not known.

The difficulty in finding a characterization of L^k₁ is due to the fact that there are infinitely many minimal forbidden 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 pendent edges at every vertex of degree 2 or 4 to get one of the families of minimal forbidden subgraphs in [2,9,10]. This does not rule out either the existence of a polynomial recognition or the possibility of forbidden subgraph characterization similar to Beineke's L²₁ family characterization.

There are some very interesting characterizations available for L^k₁ by various authors [5,6,7,8,9,10,11] based on the additional constraints minimum degree or the minimum edge degree of G.

[edit] References

• 1. L. W. Beineke, On the derived graphs and digraphs, in: Beitrage zur Graphentheorie [H. Saks et al., eds], Teubner, Leipzig (1968)pp. 17-23
• 2. Berge , C., Hypergraphs, Combinatorics of Finite sets. Amsterdam: North-Holland 1989.
• 3. Bermond, J.C., Heydemann, M.C., Sotteau, D.: Line graphs of hypergraphs I. Discrete Math. 18 235-241 (1977).
• 4. Heydemann, M. C., Scotteau, D.,: Line graphs of hypergraphs II. Colloq. MAth. Soc. J. Bolyai 18, 567-582 (1976)
• 5. M S. Jacobson, Andre E. Kezdy, and Jeno Lehel: Recognizing Intersection Graphs of Linear Uniform Hypergraphs. Graphs and Combinatorics (1977) 13: 359-367.
• 6. J. Krausz, Demonstration nouvelle d'un theorem de Whitney sur les reseaux, Mat. Fiz. Lapok 50 (1943) pp. 75-89
• 7. Van Rooij, A.C.M., Wilf, H. S.: The interchange graph of a finite graph, Acta Math. Acad. Sci. Hungar. 16 263-269 (1965).
• 8. Yury Metelsky and Regina Tyshkevich, On Line graphs of Linear 3-uniform Hypergraphs: J. of Graph Theory 25, 243-251 (1997).
• 9. Naik R. N., Rao S. B., Shrikhande S. S., and Singhi N. M., Intersection graphs of k-uniform Linear Hypergraphs, Europ. J. Combinatorics (1982) 3, 159-172.
• 10. Naik R. N., Rao S. B., Shrikhande S. S., Singhi, N. M., Intersection graphs of k-uniform hypergraphs, Ann. Discrete Math. 6(1980) 275-279
• 11. Igor E. Zverovich, A solution to a problem of Jacobson, Kezdy and Lethel, DIMACS Publications. pp 1-7 (2004)