Line graph of a hypergraph: Difference between revisions

Revision as of 17:15, 21 March 2008

Latest revision as of 17:30, 10 November 2023

(132 intermediate revisions by 40 users not shown)

Line 1:

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

{{Cleanup|date=March 2008}}

{{context}}

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 set]]s. It is a [[generalization]] of the [[line graph]] of a [[Graph (discrete mathematics)|graph]].

==Intersection (Line) graphs of Graphs ==

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

The intersection graph of a graph is usually called as Line graph and the family is denoted as L²₁. The characterization of L²₁ 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²₁ 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''.

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>

==Intersection (line) graphs of ''k''-uniform linear hypergraph ==

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

In [[mathematics]], a [[hypergraph]] is a generalization of a [[graph (mathematics)|graph]], where [[graph theory|edges]] can connect any number of [[vertex (graph theory)|vertices]]. Formally, a hypergraph is a pair <math>(X,E)</math> where <math>X</math> is a set of elements, called ''nodes'' or ''vertices'', and <math>E</math> is a set of non-empty subsets of <math>X</math> called ''hyperedges''.

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.

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

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>

The concept of Line Graphs of graphs is extended to Hypergraphs by various authors in [1,2,3].

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

Let L^k₁ stand for the family of intersection graphs of k-uniform linear hypergraphs. For larger values of k > 2, there are infinitely many minimal forbidden induced subgraphs for L^k₁. This does not rule out either the existence of polynomial recognition or the possibility of forbidden subgraph characterization (similar to Beineke's) of L²₁. There are very interesting results available for L^k₁, k > 2 by various authors. The difficulty in finding a characterization of L^k₁ is twofold. First, there are infinitely many minimal forbidden subgraphs, even for k=3. For m > 0, consider a chain of m diamonds such that consecutive diamonds share vertices of degree two. For k > 2, let us add pendent edges at every vertex of degree 2 or 4 is one family of minimal forbidden graphs. Second, many authors have suggested that there is no "Krausz-style" characterization in terms of clique covers, for k > 2.

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

<!-- Deleted image removed: [[Image:Hypergraph2.jpeg ]] -->

Let d(G) denote the minimum degree of a Graph G. Naik, Rao, Shrikhande and Singhi proved the surprising result in [1, 7, 8] that there exists a finite family of forbidden graphs for characterizing graphs of the family L^k₁ for k=3 with d(G) > 68 . In [4], Jacobson et al. improved the d(G) to 19 and gave a polynomial algorithm to decide whether a graph is a L^k₁ for k=3. The algorithm follows from a simple recursive characterization of L^k₁ and relies on the fact that there is a polynomial time recognition algorithm for members of L²₁. Jacboson et al. could not extend finite forbidden subgraph characterization proved in [7] for d(G) > 68 to 19.

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>

The complexity of recognizing members of L^k₁ without any minimum degree (edge degree) constraint is not known.

{{harvtxt|Naik|Rao|Shrikhande|Singhi|1980}}, {{harvtxt|Naik|Rao|Shrikhande|Singhi|1982}}</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]]

In [1,7,8], Naik etl al. obtained parallel results for any k > 2 under the additional condition that k³ -2k² + 1 is a lower bound on the 'edge-degree of the graph. Define the edge-degree d_e (G) of the edge uv in G as the sum of the degrees of the vertices u and v in G. Both the results in [7, 8] imply polynomial recognition algorithms for graphs under the corresponding minimum degree and minimum edge-degree conditions. Essentially in [4], Jacobson et al. extended the same method to yield a polynomial recognition algorithm for L^k₁, k > 2, provided the minimum edge-degree of the graphs is at least 2k²-3k+1. Actually this is an improvement on the cubic bound that follows from the corresponding finite characterization result in [7].

There are some interesting characterizations available for line graphs of linear ''k''-uniform hypergraphs due to various authors<ref>{{harvtxt|Naik|Rao|Shrikhande|Singhi|1980}}, {{harvtxt|Naik|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.

In [6], Metelsky and Tyshkevich, gave the finite forbidden subgraph characterization for L^k₁, k=3 with d(G) at least 19 analogous to [7]. Metelsky etl al. characterized Line graphs of Graphs with d(G) > 4 in terms of fewer number of forbidden induced subgraphs from the set of nine Beineke graphs. Furthermore, they also proved that for k > 3 and an arbitrary constant c, L^k₁ with d(G) > c) cannot be characterized by a finite list of forbidden induced subgraphs.

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|2009}}</ref> reduced the minimum degree to 10.

In [10], Zverovivh proved that for k > 2, there exists a finite family of forbidden graphs for characterizing the graphs with minimum edge-degree condition stated in [6] for L^k₁.

There are many interesting open problems and conjectures in Naik et al., Jacoboson et al., Metelsky et al. and Zverovich.

==References==

== Disjointness graph ==

* 1. Berge , C., Hypergraphs, Combinatorics of Finite sets. Amsterdam: North-Holland 1989.

The '''disjointness graph''' of a hypergraph ''H'', denoted D(''H''), is the graph whose vertex set is the set of the hyperedges of ''H'', with two vertices adjacent in D(''H'') when their corresponding hyperedges are ''disjoint'' in ''H''.<ref>{{Cite journal|last=Meshulam|first=Roy|date=2001-01-01|title=The Clique Complex and Hypergraph Matching|journal=Combinatorica|language=en|volume=21|issue=1|pages=89–94|doi=10.1007/s004930170006|s2cid=207006642|issn=1439-6912}}</ref> In other words, D(''H'') is the [[complement graph]] of L(''H''). A [[Clique (graph theory)|clique]] in D(''H'') corresponds to an independent set in L(''H''), and vice versa.

* 2. Bermond, J.C., Heydemann, M.C., Sotteau, D.: Line graphs of hypergraphs I. Discrete Math. 18 235-241 (1977).

* 3. Heydemann, M. C., Scotteau, D,: Line graphs of hypergraphs II. Colloq. MAth. Soc. J. Bolyai 18, 567-582 (1976)

== References ==

* 4. M S. Jacobson, Andre E. Kezdy, and Jeno Lehel: Recognizing Intersection Graphs of Linear Uniform Hypergraphs. Graphs and Combinatorics (1977) 13: 359-367.

{{Reflist}}

* 5. J. Krausz, Demonstration nouvelle d'un theorem de Whitney sur les reseaux, Mat. Fiz. Lapok 50 (1943) pp. 75-89

*{{citation

* 6. Yury Metelsky and Regina Tyshkevich, On Line graphs of Linear 3-uniform Hypergraphs: J. of Graph Theory 25, 243-251 (1997).

| first = L. W. | last = Beineke

* 7. Naik R. N., Rao S. B., Shrikhande S. S, and Singhi N. M., Intersection graphs of k-uniform Linear Hypergraphs, Europ. J. Combinatorics (1982) 3, 159-172.

| contribution = On derived graphs and digraphs

* 8. Naik R. N., Rao S. B., Shrikhande S. S, Singhi, N. M, Intersection graphs of k-uniform hypergraphs, Ann. Discrete Math. 6(1980) 275-279

* | 9.title L. W. Beineke, On the derived graphs and digraphs, in:= Beitrage zur Graphentheorie [H. Saks et al., eds), Teubner, Leipzig (1968)pp. 17-23

| editor1-first = H. | editor1-last = Sachs

* 10. Igor E. Zverovich, A solution to a problem of Jacobson, Kezdy and Lethel, DIMACS Publications. pp 1-7 (2004)

| editor2-first = H. | editor2-last = Voss

* 11. Van Rooij, A.C.M., Wilf, H. S: The interchange graph of a finite graph, Acta Math. Acad. Sci. Hungar. 16 263-269 (1965).

| editor3-first = H. | editor3-last = Walther

| publisher = Teubner | ___location = Leipzig | pages = 17–23 | year = 1968}}.

*{{citation|last=Berge|first=C.|title=Hypergraphs: Combinatorics of Finite Sets|year=1989|___location=Amsterdam|publisher=North-Holland|mr=1013569|authorlink=Claude Berge}}. Translated from the French.

*{{citation

| first1 = J. C. | last1 = Bermond

| first2 = M. C. | last2 = Heydemann

| 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

}}.

*{{citation

| first1 = M. C. | last1 = Heydemann

| first2 = D. | last2 = Sotteau

| contribution = Line graphs of hypergraphs II

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

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

| volume = 18 | pages = 567–582 | year = 1976 |mr=0519291}}.

*{{citation

| last = Krausz | first = J.

| title = Démonstration nouvelle d'une théorème de Whitney sur les réseaux

| journal = Mat. Fiz. Lapok | volume = 50 | year = 1943 | pages = 75–85

|mr=0018403}}. (In Hungarian, with French abstract.)

*{{citation

| first = L. | last = Lovász | authorlink = László Lovász

| contribution = Problem 9

| title = Beiträge zur Graphentheorie und deren Anwendungen

| series = Vorgetragen auf dem Internationalen Kolloquium in Oberhof (DDR)

| year = 1977 | page = 313}}.

*{{citation

| first1 = M. S. | last1 = Jacobson

| first2 = Andre E. | last2 = Kézdy

| first3 = Jeno | last3 = Lehel

| title = Recognizing intersection graphs of linear uniform hypergraphs

| journal = [[Graphs and Combinatorics]] | volume = 13 | pages = 359–367 | year = 1997

| issue = 4

|mr=1485929 | doi = 10.1007/BF03353014| s2cid = 9173731

}}.

*{{citation

| first1 = Yury | last1 = Metelsky

| first2 = Regina | last2 = Tyshkevich

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

| journal = Journal of Graph Theory | volume = 25 | issue = 4

| pages = 243–251

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

*{{citation

| first1 = Ranjan N. | last1 = Naik

| first2 = S. B. | last2 = Rao

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

| first4 = N. M. | last4 = Singhi

| contribution = Intersection graphs of ''k''-uniform hypergraphs

| title = Combinatorial mathematics, optimal designs and their applications (Proc. Sympos. Combin. Math. and Optimal Design, Colorado State Univ., Fort Collins, Colo., 1978)

| series = Annals of Discrete Mathematics | volume = 6 | pages = 275–279 | year = 1980

|mr=0593539}}.

*{{citation

| first1 = Ranjan N. | last1 = Naik

| first2 = S. B. | last2 = Rao

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

| first4 = N. M. | last4 = Singhi

| title = Intersection graphs of ''k''-uniform linear hypergraphs

| journal = European Journal of Combinatorics | volume = 3 | pages = 159–172 | year = 1982

| issue = 2

|mr=0670849 | doi=10.1016/s0195-6698(82)80029-2| doi-access = free }}.

*{{citation

| first1 = P. V. | last1 = Skums

| first2 = S. V. | last2 = Suzdal'

| first3 = R. I. | last3 = Tyshkevich

| title = Edge intersection of linear 3-uniform hypergraphs

| journal = Discrete Mathematics

| volume = 309 | pages = 3500–3517 | year = 2009 | doi=10.1016/j.disc.2007.12.082| doi-access = free}}.

*{{citation

| first = Igor E. | last = Zverovich

| title = A solution to a problem of Jacobson, Kézdy and Lehel

| journal = [[Graphs and Combinatorics]] | volume = 20 | issue = 4 | year = 2004 | pages = 571–577

|mr=2108401 | doi = 10.1007/s00373-004-0572-1| s2cid = 33662052

}}.

*{{citation

| first = Vitaly I. | last = Voloshin

| title = Introduction to Graph and Hypergraph Theory

| ___location = New York | publisher = [[Nova Science Publishers, Inc.]] | year = 2009

|mr=2514872}}

[[Category:Graph families]]

[[Category:Hypergraphs]]