Line graph of a hypergraph: Difference between revisions

Revision as of 22:50, 11 March 2008

Revision as of 00:05, 12 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 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 graph]]s 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 Line graphsL²₁ 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^k2₁. 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(gG) 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 Line graphs of graphsL²₁. In [4] Jacboson et al. could not extend finite forbidden subgraph characterization proved in [7] for the d(G)> at least 6968 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_v (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.