An illustration of the Lovász–Woodall conjecture in the Petersen graph: the graph is 3-connected, and 3 edges lie on a common cycle.

In graph theory, the Lovász–Woodall conjecture is a long-standing problem on cycles in graphs. It says:

If G is a k-connected graph and L is a set of k independent edges in G, then G has a cycle containing L, unless k is odd and L is an edge cut.

It was proposed independently by László Lovász[1] in 1974 and by D. R. Woodall[2] in 1977.

Background and motivation

Many results in graph theory, starting with Menger's theorem, guarantee the existence of paths or cycles in a k-connected graph. For 2-connected graphs, Menger's theorem is equivalent to the statement that any two vertices lie on a common cycle. A theorem of G. A. Dirac generalizes this claim: if a graph is k-connected for k ≥ 2, then for every set of k vertices in the graph there is a cycle that passes through all the vertices in the set.[3]

Another corollary of Menger's theorem is that in 2-connected graphs, any two edges lie on a common cycle. The proof, however, does not generalize to the corresponding statement for k edges in a k-connected graph; rather, Menger's theorem can be used to show that in a k-connected graph, given any 2 edges and k-2 vertices, there is a cycle passing through all of them.[4]

There is one obstacle to the stronger claim that in a k-connected graph G, given any set L of k edges, there should be a cycle containing L. Suppose that the edges in L form an edge cut: the vertices of G can be separated into two sets A and B such that the edges in L all join a vertex in A to a vertex in B, and are the only edges to do so. Then any cycle in G can only use an even number of edges of L: it must cross from A to B and from B back to A an equal number of times. If k is odd, this means that no cycle can contain all of L.

The Lovász–Woodall conjecture states that this is the only obstacle: given any set L of k edges, there is a cycle containing L, except in the case that k is odd and L is an edge cut.

Woodall proposed the conjecture as one of several possible statements[2] that would imply a conjecture made by Claude Berge: given a k-connected graph G with independence number α(G), and any subgraph F of G with at most k-α(G) edges whose components are all paths, G has a Hamiltonian cycle containing F.[5] In 1982, Roland Häggkvist and Carsten Thomassen proved Berge's conjecture by proving one of the weaker statements proposed by Woodall.[6]

Partial results

As mentioned above, the k = 2 case of the Lovász–Woodall conjecture follows from Menger's theorem. The k = 3 case was given as an exercise by Lovász.[7] After the conjecture was made, it was proven for k = 4 by Péter L. Erdős and E. Győri[8] and independently by Michael V. Lomonosov.[9], and for k = 5 by Daniel P. Sanders.[10]

Other partial progress toward the conjecture has included versions of the result with a stronger assumption on connectivity. Woodall's paper[2] included a proof that the conclusion of the conjecture holds if G is (2k-2)-connected, and in 1977, Thomassen proved that the conjecture holds if G is (3k-1)/2-connected.[11] In 1982, Häggkvist and Thomassen proved that the conjecture holds if G is (k+1)-connected.[6]

In 2002, Ken-ichi Kawarabayashi proved that under the hypotheses of the conjecture, L is either contained in a cycle of G or in two disjoint cycles.[7]

Current status

In two publications in 2002[7] and 2008,[12] Kawarabayashi claimed to have a proof on the conjecture, giving an outline for the proof and leaving several steps to future publications, but the full proof has not been published since.

References

  1. Lovász, László (1974), "Problem 5", Period. Math. Hungar., 4: 82
  2. 1 2 3 Woodall, D. R. (1977), "Circuits containing specified edges", J. Comb. Theory Ser. B, 22 (3): 274–278, doi:10.1016/0095-8956(77)90072-7
  3. Dirac, Gabriel Andrew (1960). "In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen". Mathematische Nachrichten. 22 (1–2): 61–85. doi:10.1002/mana.19600220107. MR 0121311..
  4. Berge, Claude (1973). Graphs and Hypergraphs. North-Holland Publishing Company. pp. 169–170. ISBN 0-444-10399-6.
  5. Berge, p. 214
  6. 1 2 Häggkvist, Roland; Thomassen, Carsten (1982), "Circuits through specified edges", Discrete Mathematics, 41 (1): 29–34, doi:10.1016/0012-365X(82)90078-4
  7. 1 2 3 Kawarabayashi, Ken-ichi (2002), "One or two disjoint circuits cover independent edges. Lovász-Woodall conjecture", Journal of Combinatorial Theory, Series B, 84 (1): 1–44, doi:10.1006/jctb.2001.2059, MR 1877899
  8. Erdős, Péter L.; Győri, E. (1985), "Any four independent edges of a 4-connected graph are contained in a circuit", Acta Mathematica Hungarica, 46 (3–4): 311–313, doi:10.1007/BF01955745, MR 0832725, S2CID 122211600
  9. Lomonosov, Michael V. (1990), "Cycles through prescribed elements in a graph", in Korte, Bernhard; Lovász, László; Prömel, Hans Jürgen; Schrijver, Alexander (eds.), Paths, flows, and VLSI-layout: Papers from the meeting held at the University of Bonn, Bonn, June 20–July 1, 1988, Algorithms and Combinatorics, vol. 9, Berlin: Springer-Verlag, pp. 215–234, ISBN 3-540-52685-4, MR 1083381
  10. Sanders, Daniel P. (1996), "On circuits through five edges", Discrete Mathematics, 159 (1–3): 199–215, doi:10.1016/0012-365X(95)00079-C, MR 1415294
  11. Thomassen, Carsten (1977), "Note on circuits containing specified edges", Journal of Combinatorial Theory, Series B, 22 (3): 279–280, doi:10.1016/0095-8956(77)90073-9
  12. Kawarabayashi, Ken-ichi (2008), "An improved algorithm for finding cycles through elements", in Lodi, Andrea; Panconesi, Alessandro; Rinaldi, Giovanni (eds.), Integer Programming and Combinatorial Optimization, 13th International Conference, IPCO 2008, Bertinoro, Italy, May 26-28, 2008, Proceedings, Lecture Notes in Computer Science, vol. 5035, Springer, pp. 374–384, doi:10.1007/978-3-540-68891-4_26
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.