Line graphs of hypergraphs
Encyclopedia
The line graph of a hypergraph is the graph
whose vertex set is the set of the hyperedges of the hypergraph
, with two edges adjacent when they have 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.
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 .
s.) No characterization by forbidden induced subgraphs is known of line graphs of k-uniform hypergraphs for any k ≥ 3, and showed there is no such characterization by a finite list if k = 3.
characterized line graphs of graphs in terms of clique
covers. (See Line Graphs.) A global characterization of Krausz type for the line graphs of k-uniform hypergraphs for any k ≥ 3 was given by .
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
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.
There are some interesting characterizations available for line graphs of linear k-uniform hypergraphs due to various authors under constraints on the minimum degree or the minimum edge degree of G. Minimum edge degree at least k3-2k2+1 in is reduced to 2k2-3k+1 in and to characterize line graphs of k-uniform linear hypergraphs for any k ≥ 3.
The complexity of recognizing line graphs of linear k-uniform hypergraphs without any constraint on minimum degree (or minimum edge-degree) is not known. For k = 3 and minimum degree at least 19, recognition is possible in polynomial time ( and ). reduced the minimum degree to 10.
There are many interesting open problems and conjectures in Naik et al., Jacoboson et al., Metelsky et al. and Zverovich.
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
whose vertex set is the set of the hyperedges of the hypergraph
Hypergraph
In mathematics, a hypergraph is a generalization of a graph, where an edge can connect any number of vertices. Formally, a hypergraph H is a pair H = where X is a set of elements, called nodes or vertices, and E is a set of non-empty subsets of X called hyperedges or links...
, with two edges adjacent when they have nonempty intersection. In other words, the line graph of a hypergraph is the intersection graph
Intersection graph
In the mathematical area of graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph may be represented as an intersection graph, but some important special classes of graphs may be defined by the types of sets that are used to form...
of a family of finite sets. It is a generalization of the line graph
Line graph
In graph theory, the line graph L of undirected graph G is another graph L that represents the adjacencies between edges of G...
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.
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 .
Line graphs of k-uniform hypergraphs, k ≥ 3
characterized line graphs of graphs by a list of 9 forbidden induced subgraphs. (See the article on line graphLine graph
In graph theory, the line graph L of undirected graph G is another graph L that represents the adjacencies between edges of G...
s.) No characterization by forbidden induced subgraphs is known of line graphs of k-uniform hypergraphs for any k ≥ 3, and showed there is no such characterization by a finite list if k = 3.
characterized line graphs of graphs in terms of clique
Clique (graph theory)
In the mathematical area of graph theory, a clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs...
covers. (See Line Graphs.) A global characterization of Krausz type for the line graphs of k-uniform hypergraphs for any k ≥ 3 was given by .
Line graphs of k-uniform linear hypergraphs, k ≥ 3
A global characterization of Krausz type for the line graphs of k-uniform linear hypergraphs for any k ≥ 3 was given by . At the same time, they found a finite list of forbidden induced subgraphs for linear 3-uniform hypergraphs with minimum vertex degree at least 69. and improved this bound to 19. At last reduced this bound to 16. also proved that, if k > 3, no such finite list exists for linear k-uniform hypergraphs, no matter what lower bound is placed on the degree.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
Diamond graph
In the mathematical field of graph theory, the diamond graph is a planar undirected graph with 4 vertices and 5 edges. It consists of a complete graph K_4 minus one edge....
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
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.
There are some interesting characterizations available for line graphs of linear k-uniform hypergraphs due to various authors under constraints on the minimum degree or the minimum edge degree of G. Minimum edge degree at least k3-2k2+1 in is reduced to 2k2-3k+1 in and to characterize line graphs of k-uniform linear hypergraphs for any k ≥ 3.
The complexity of recognizing line graphs of linear k-uniform hypergraphs without any constraint on minimum degree (or minimum edge-degree) is not known. For k = 3 and minimum degree at least 19, recognition is possible in polynomial time ( and ). reduced the minimum degree to 10.
There are many interesting open problems and conjectures in Naik et al., Jacoboson et al., Metelsky et al. and Zverovich.