Content deleted Content added
Tangi-tamma (talk | contribs) mNo edit summary |
Tangi-tamma (talk | contribs) |
||
Line 2:
{{context}}
==Intersection (
The intersection graph of a graph is usually called as Line graph and the family is denoted as L<sup>2</sup><sub>1</sub>. The characterization of L<sup>2</sup><sub>1</sub> 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<sup>2</sup><sub>1</sub> in terms of [[Clique]] covers is given by J. Krausz [5]. In Rooij and Wilf's proof [11], 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''.▼
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''. ▼
==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 graphs are 2-uniform linear hypergraphs (a simple graph is loopless and contains no multiple edges).▼
▲In [[mathematics]], a
▲The intersection graph of a graph is usually called as Line graph and the family is denoted as L<sup>2</sup><sub>1</sub>. The characterization of L<sup>2</sup><sub>1</sub> 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<sup>2</sup><sub>1</sub> in terms of [[Clique]] covers is given by J. Krausz [5]. In Rooij and Wilf's proof [11], 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''.
▲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<sup>k</sup><sub>1</sub> 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<sup>k</sup><sub>1</sub>. This does not rule out either the existence of polynomial recognition or the possibility of forbidden subgraph characterization (similar to Beineke's) of L<sup>2</sup><sub>1</sub>. There are very interesting results available for L<sup>k</sup><sub>1</sub>, k > 2 by various authors. The difficulty in finding a characterization of L<sup>k</sup><sub>1</sub> 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.
| |||