Line graph of a hypergraph: Difference between revisions

Revision as of 19:31, 3 May 2014

Revision as of 11:35, 5 May 2014

Line 1:

The '''line graph of a hypergraph''' is the [[graph (mathematics)|graph]] whose vertex set is the set of the hyperedges of the [[hypergraph]], with two hyperedges adjacent when they have a nonempty intersection. In other words, the line graph of a hypergraph is the [[intersection graph]] of a family of finite sets. It is a generalization of the [[line graph]] of a graph.

Questions about line graphs of hypergraphs are often generalizations of questions about line graphs of graphs. For instance, a hypergraph whose edges all have size ''k'' is called ''k''' ''-uniform'''. (A 2-uniform hypergraph is a graph.). In hypergraph theory, it is often natural to require that hypergraphs be ''k''-uniform. Every graph is the line graph of some hypergraph, but, given a fixed edge size ''k'', not every graph is a line graph of some ''k''-uniform hypergraph. A main problem is to characterize those that are, for each ''k'' ≥ 3.

Line 7:

==Line graphs of ''k''-uniform hypergraphs, ''k'' ≥ 3==

{{harvtxt|Beineke|1968}} characterized line graphs of graphs by a list of 9 [[forbidden induced subgraph]]s. (See the article on [[line graph]]s.) No characterization by forbidden induced subgraphs is known of line graphs of k-uniform hypergraphs for any ''k'' ≥ 3, and {{harvtxt|Lovász|1977}} showed there is no such characterization by a finite list if ''k'' = 3.

{{harvtxt|Krausz|1943}} characterized line graphs of graphs in terms of [[clique (graph theory)|clique]] covers. (See [[Line_graphLine graph#Characterization_and_recognitionCharacterization and recognition|Line Graphs]].) A global characterization of Krausz type for the line graphs of ''k''-uniform hypergraphs for any ''k'' ≥ 3 was given by {{harvtxt|Berge|1989}}.

==Line graphs of ''k''-uniform linear hypergraphs, ''k'' ≥ 3==

Line 16:

The difficulty in finding a characterization of linear ''k''-uniform hypergraphs is due to the fact that there are infinitely many forbidden induced subgraphs. To give examples, for ''m'' > 0, consider a chain of ''m'' [[diamond graph]]s such that the consecutive diamonds share vertices of degree two. For ''k'' ≥ 3, add pendant edges at every vertex of degree 2 or 4 to get one of the families of minimal forbidden subgraphs of

{{harvs|last1 = Naik|last2 = Rao|last3 = Shrikhande|last4 = Singhi|year = 1980|year2 = 1982|txt = yes}} as shown here. This does not rule out either the existence of a polynomial recognition or the possibility of a forbidden induced subgraph characterization similar to Beineke's of line graphs of graphs.

[[Image:Repeated diamond graph.svg|350px|center]]

Line 57:

| title = Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976)

| series = Colloq. Math. Soc. J. Bolyai

| volume = 18 | pages = 567–582 | year = 1976 | id = {{MathSciNet | id = 0519291}}}}.

*{{citation

Line 85:

| year = 1997 | title = On line graphs of linear 3-uniform hypergraphs

| journal = Journal of Graph Theory | volume = 25 | pages = 243–251

| id = {{MathSciNet | id = 1459889}} | doi = 10.1002/(SICI)1097-0118(199708)25:4<243::AID-JGT1>3.0.CO;2-K}}.

*{{citation