Content deleted Content added
No edit summary |
What a mess. It does not attempt to tell the non-mathematician reader at the outset that mathematics is what this is about, nor to tell the mathematician who may not know, what a hypergraph is. |
||
Line 1:
{{cleanup}}
{{context}}
==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). 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''.
| |||