Line graph of a hypergraph: Difference between revisions

Revision as of 00:24, 14 March 2008

Revision as of 00:29, 14 March 2008

Line 1:

==Intersection (Line) graphs of k-uniform linear [[Hypergraph]] ==

A hypergraph is '''linear''' if any two edges have at most one common vertex. Two edges are '''r-intersecting''' if they share at least r common vertices. '''A k-uniform''' hypergraph is a hypegraph with each edge of size k. Note that graphs are 2-uniform linear hypergraphs (a simple graph is loopless and contains no multiple edges). The intersection graph of a graph is usually called as Line graph and the family is denoted as L²₁. The characterization of L²₁ the [[Line graph]]s was solved by Van Rooij and Wilf and by Beineke [9]. Beineke's (finite) forbidden subgraph characterization immediately implies a polynomial algorithm to recognize line graphs. A characterization of L²₁ in terms of [[Clique]] covers is given by J. Krausz [5]. In Rooij and Wilf's proof [11], the notion of even and odd triangles was introduced to characterize line graphs. A tringle in a graph G is called ''even'' if every vertex of the graph G is adjecent to either 0 or 2 vertices, otherwise the triangle is called ''odd''.

Let L^k₁ stand for the family of intersection graphs of k-uniform linear hypergraphs. For larger values of k > 2, there are infinitely many minimal forbidden induced subgraphs for L^k₁. This does not rule out either the existence of polynomial recognition or the possibility of forbidden subgraph characterization (similar to Beineke's) of L²₁. There are very interesting results available for L^k₁, k > 2 by various authors. The difficulty in finding a characterization of L^k₁ is twofold. First, there are infinitely many minimal forbidden subgraphs, even for k=3. For m > 0, consider a chain of m diamonds (figure 1) such that consecutive diamonds share vertices of degree two. For k > 2, let us add pendent edges at every vertex of degree 2 or 4 is one family of minimal forbidden graphs. Second, many authors have suggested that there is no "Krausz-style" characterization in terms of clique covers, for k > 2.

Line 28:

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

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

* 11. VAn Rooij, A.C.M., Wilf, H. S: The interchange graph of a finite graph, Acta Math. Acad. Sci. Hungar. 16 263-269 (1965).