Line graph of a hypergraph: Difference between revisions

Revision as of 03:38, 17 March 2008

Latest revision as of 17:30, 10 November 2023

(137 intermediate revisions by 40 users not shown)

Line 1:

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

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

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

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

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.

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

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

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>

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

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

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

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.

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.

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>

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

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

In progress...

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.

==References==

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>

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

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

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

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

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

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

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.

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

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

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.

* 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. L. W. Beineke, On the derived graphs and digraphs, in: Beitrage zur Graphentheorie [H. Saks et al., eds), Teubner, Leipzig (1968)pp. 17-23

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

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

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

== Disjointness graph ==

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.

== References ==

{{Reflist}}

*{{citation

| first = L. W. | last = Beineke

| contribution = On derived graphs and digraphs

| title = Beitrage zur Graphentheorie

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

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

| 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]]