Line graph of a hypergraph: Difference between revisions

Revision as of 15:49, 6 July 2021

Revision as of 07:33, 27 June 2022

Line 1:

{{short description|Generalization of line graphs to hypergraphs}}

In [[graph theory]], particularly in the theory of [[hypergraph]]s, the '''line graph of a hypergraph''' ''H'', denoted L(''H''), is the [[graph (discrete mathematics)|graph]] whose vertex set is the set of the hyperedges of ''H'', with two vertices adjacent in L(''H'') when their corresponding hyperedges have a nonempty intersection in ''H''. In other words, L(''H'') is the [[intersection graph]] of a family of finite sets. It is a generalization of the [[line graph]] of a graph.

In [[graph theory]], particularly in the theory of [[hypergraph]]s, the '''line graph of a hypergraph''' ''{{mvar|H''}}, denoted {{math|L(''H'')}}, is the [[graph (discrete mathematics)|graph]] whose [[Vertex (graph theory)|vertex]] set is the [[Set (mathematics)|set]] of the hyperedges of ''{{mvar|H''}}, with two vertices adjacent in {{math|L(''H'')}} when their corresponding hyperedges have a nonempty [[intersection]] in ''{{mvar|H''}}. In other words, {{math|L(''H'')}} is the [[intersection graph]] of a family of [[finite setsset]]s. It is a [[generalization]] of the [[line graph]] of a [[Graph (discrete mathematics)|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.

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 ''{{mvar|k''}} is called {{nowrap|'''{{mvar|k'''''}}-uniform'''}}{. (A 2-uniform hypergraph is a graph). In hypergraph theory, it is often natural to require that hypergraphs be ''{{nowrap|{{mvar|k''}}-uniform}}. Every graph is the line graph of some hypergraph, but, given a fixed edge size ''{{mvar|k''}}, not every graph is a line graph of some ''{{nowrap|{{mvar|k''}}-uniform}} hypergraph. A main problem is to characterize those that are, for each {{math|''k'' ≥ 3}}.

A hypergraph is '''linear''' if each pair of hyperedges intersects in at most one vertex. Every graph is the line graph, not only of some hypergraph, but of some linear hypergraph {{harv|Berge|1989}}.