Line graph of a hypergraph: Difference between revisions

Revision as of 23:23, 13 March 2008

Revision as of 00:24, 14 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 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, 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 foof clique covers, for k > 2.

Let d(G) denote the minimum degree of a Graph G. Naik, Rao, Shrikhande and Singhi proved the surprising result in [7, 8] that there exists a finite family of forbidden graphs for characterizing graphs of the family L^k₁ for k=3 with d(g) > 68 . 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 d(G) > 68 to 19.

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

In [7,8], Naik etl al. 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, 8] imply polynomial recognition algorithms for graphs under the corresponding minimum degree and minimum edge-degree conditions. Essentially in [4], Jacobson et al. 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) > 4 in terms of fewer number of forbidden induced subgraphs 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) > (c-1) cannot be characterized by a finite list of forbidden induced subgraphs.

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

In progress...

Line 19:

* 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.