Line graph of a hypergraph: Difference between revisions

Revision as of 17:15, 21 March 2008

Revision as of 17:24, 21 March 2008

Line 10:

In [[mathematics]], a [[hypergraph]] is a generalization of a [[graph (mathematics)|graph]], where [[graph theory|edges]] can connect any number of [[vertex (graph theory)|vertices]]. Formally, a hypergraph is a pair <math>(X,E)</math> where <math>X</math> is a set of elements, called ''nodes'' or ''vertices'', and <math>E</math> is a set of non-empty subsets of <math>X</math> called ''hyperedges''.

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 concept of Line Graphs of graphs is extended to Hypergraphs by various authors in [1,2,3].

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

<!-- Deleted image removed: [[Image:Hypergraph2.jpeg ]] -->

Let d(G) denote the minimum degree of a Graph G. Naik, Rao, Shrikhande and Singhi proved the surprising result in [1, 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²₁. 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 (edge degree) constraint is not known.

In [1,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) 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₁.

==References==