Line graph of a hypergraph: Difference between revisions

Revision as of 16:21, 16 March 2008

Revision as of 03:38, 17 March 2008

Line 1:

==Intersection (Lineline) graphs of ''k''-uniform linear [[Hypergraphhypergraph]] ==

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