Line graph of a hypergraph: Difference between revisions

Revision as of 22:25, 11 March 2008

Revision as of 22:50, 11 March 2008

Line 2:

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 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 graphs 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. Let d(G) denote the minimum degree of the graph G. 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 particular families of graphsL^k₁. For r=1 thereThere are very interesting results available for L^{k-uniform hypergraphs}₁, k > 2 by various authors. The difficulty in finding a characterization of r-intersection graphsL^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. Rao, Singhi, Shrikhande proved the surprising result in [7] that there exists a finite family of forbidden graphs for characterizing graphs with minimumd(g) degree at> least 6968 which are intersectionL^k₁ graphs of linearfor k=3-uniform hypergraphs. In [4], Jacobson et al. improved the minimumd(g) degreeto condition to 19 and gave a polynomial algorithm to decide whether a graph is a linearL^k₁ intersection graph offor k=3-uniform hypergraph. The algorithm follows from a simple recursive characterization of graphs of liner Intersection grpahs of L^{k-uniform hypergraphs}₁ and relies on the fact that there is a polynomial time recognition algorithm for members of Line graphs of graphs. In [4] Jacboson et al. could not extend finite forbidden subgraph characterization proved for the minimum degreed(G) at least 69 to 19.

to minimum degree 19.

The complexity of recognizing members of intersection graphs of linear 3-uniform hypergraphs without any minimum degree constraint is not known.

The complexity of recognizing members of intersection graphs of linear 3-uniform hypergraphsL^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 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 garphs under the corresponding minimum degree and minimum edge-degree conditions.

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 garphsgraphs under the corresponding minimum degree and minimum edge-degree conditions.

In [6] Metelsky and Tyshkevich, gave the finite forbidden subgraph characterization for linear 3-uniform hypergraphs with minimum degree at least 19 in G analogous to [7]. Metelsky etl al. characterized Line graphs of Graphs with minimum degree condition with minimum degree 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, the set of all Intersection graphs of k-uniform linear hypergraphs with minium degree at least c cannot be characterized by a finite list of forbidden induced subgraphs.

In [6] Metelsky and Tyshkevich, gave the finite forbidden subgraph characterization for linearL^k₁, k=3-uniform hypergraphs with minimum degreed(g) at least 19 in G analogous to [7]. Metelsky etl al. characterized Line graphs of Graphs with minimum degree condition with minimum degreed(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, the set of all Intersection graphs of L^{k-uniform linear hypergraphs}₁ with minium degreed(G) at least c cannot be characterized by a finite list of forbidden induced subgraphs.

In progress...