Line graph of a hypergraph: Difference between revisions

Revision as of 15:49, 6 July 2021

Latest revision as of 17:30, 10 November 2023

(2 intermediate revisions by one other user not shown)

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}}.

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 .<ref>{{harv|Berge|1989}}.</ref>

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

Beineke<ref>{{harvtxt|Beineke|1968}}</ref> 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 Lovász<ref>{{harvtxt|Lovász|1977}}</ref> showed there is no such characterization by a finite list if ''k'' = 3.

Krausz<ref>{{harvtxt|Krausz|1943}}</ref> characterized line graphs of graphs in terms of [[clique (graph theory)|clique]] covers. (See [[Line graph#Characterization 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 Berge<ref>{{harvtxt|Berge|1989}}.</ref>

==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 Naik, Rao, Shrikhande, and Singhi.<ref>{{harvtxt|Naik|Rao|Shrikhande|Singhi|1980}}.</ref> 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. Metelsky|l and Tyshkevich<ref>{{harvtxt|Metelsky|Tyshkevich|1997}}</ref> and Jacobson, Kézdy, and Lehel<ref>{{harvtxt|Jacobson|Kézdy|Lehel|1997}}</ref> improved this bound to 19. At last Skums, Suzdal', and Tyshkevich<ref>{{harvtxt|Skums|Suzdal'|Tyshkevich|20052009}}</ref> reduced this bound to 16. Metelsky and Tyshkevich<ref>{{harvtxt|Metelsky|Tyshkevich|1997}}</ref> 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]]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 Naik, Rao, Shrikhande, and Singhi<ref>

{{harvsharvtxt|last1 = Naik|last2 = Rao|last3 = Shrikhande|last4 = Singhi|year1980}}, = 1980{{harvtxt|Naik|Rao|Shrikhande|Singhi|year2 = 1982|txt = yes}}</ref> 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]]

There are some interesting characterizations available for line graphs of linear ''k''-uniform hypergraphs due to various authors (<ref>{{harvsharvtxt|last1 = Naik|last2 = Rao|last3 = Shrikhande|last4 = Singhi|year = 1980|year2}}, = 1982{{harvtxt|nb = yesNaik|Rao|Shrikhande|Singhi|1982}}, {{harvnb|Jacobson|Kézdy|Lehel|1997}}, {{harvnb|Metelsky|Tyshkevich|1997}}, and {{harvnb|Zverovich|2004}})</ref> under constraints on the minimum degree or the minimum edge degree of G. Minimum edge degree at least ''k''³-2''k''²+1 in Naik, Rao, Shrikhande, and Singhi<ref>{{harvtxt|Naik|Rao|Shrikhande|Singhi|1980}}</ref> is reduced to 2''k''²-3''k''+1 in Jacobson, Kézdy, and Lehel<ref>{{harvtxt|Jacobson|Kézdy|Lehel|1997}}</ref> and Zverovich<ref>{{harvtxt|Zverovich|2004}}</ref> 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 (.<ref>{{harvnb|Jacobson|Kézdy|Lehel|1997}} and {{harvnb|Metelsky|Tyshkevich|1997}}).</ref> Skums, Suzdal', and Tyshkevich<ref>{{harvtxt|Skums|Suzdal'|Tyshkevich|20052009}}</ref> 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.

Line 45 ⟶ 47:

| first3 = D. | last3 = Sotteau

| title = Line graphs of hypergraphs I

| journal = [[Discrete Mathematics (journal)|Discrete Mathematics]] | volume = 18 | pages = 235–241 | year = 1977

| issue = 3

|mr=0463003 | doi = 10.1016/0012-365X(77)90127-3| url = https://hal.inria.fr/hal-02360671/file/21-BHS77-L%28H%29.pdf

Line 90 ⟶ 92:

*{{citation

| first1 = Ranjan N. | last1 = Naik

| first2 = S. B. | last2 = Rao

| first3 = S. S. | last3 = Shrikhande | authorlink3 = S. S. Shrikhande