Line graph of a hypergraph

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 simple graphs are 2-uniform linear hypergraphs (a simple graph is loopless and contains no multiple edges). The intersection graph of a graph L²₁ is usually called as Line graph. The characterization of Line graphs for Graphs was solved by Van Rooij and Wilf and by Beineke. 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. In Rooij and Wilf's proof, 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. 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 fo clique covers, for k > 2.

Let d(G) denote the minimum degree of a Graph G. Rao, Singhi, Shrikhande proved the surprising result in [7] that there exists a finite family of forbidden graphs for characterizing graphs with d(g) > 68 which are L^k₁ for k=3. In [4], Jacobson et al. improved the d(G) to 19 and gave a polynomial algorithm to decide whether a graph is a L^k₁ for k=3. The algorithm follows from a simple recursive characterization of L^k₁ and relies on the fact that there is a polynomial time recognition algorithm for members of L²₁. In [4] Jacboson et al. could not extend finite forbidden subgraph characterization proved in [7] for the d(G)> 68 to 19.

The complexity of recognizing members of L^k₁ without any minimum degree constraint is not known.

In [7], Rao obtained parallel results for any k > 2 under the additional condition that k³ -2k² + 1 is a lower bound on the 'edge-degree of the graph. Define the edge-degree d_e (G) of the edge uv in G as the sum of the degrees of the vertices u and v in G. Both the results in [7] imply polynomial recognition algorithms for graphs under the corresponding minimum degree and minimum edge-degree conditions. Essentially they they extended the same method to yield a polynomial recognition algorithm for L^k₁, k > 2, provided the minimum edge-degree of the graphs is at least 2k²-3k+1. actually this is an improvement on the cubic bound that follows from the corresponding finite characterization result in [7].

In [6] Metelsky and Tyshkevich, gave the finite forbidden subgraph characterization for L^k₁, k=3 with d(g) at least 19 analogous to [7]. Metelsky etl al. characterized Line graphs of Graphs with d(g) at least 5 in terms of fewer number of forbidden induced subgraph from the set of nine Beineke graphs. Furthermore, they also proved that for k > 3 and an arbitrary constant c, L^k₁ with d(G) at least c cannot be characterized by a finite list of forbidden induced subgraphs.

In [8] Zverovivh proved that there exists a finite family of forbidden graphs for characterizing the graphs with minimum edge-degree condition stated in [6] for L^k₁ for K > 2.

In progress...

References

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