Li, Wu, Meng and Ma's kk-tree connectivity conjecture for line graphs

About 6 years old · traced to

Let GG be a connected graph with at least kk vertices and at least kk edges, and let L(G)L(G) be its line graph. For a set S⊆V(G)S\subseteq V(G) with ∣S∣≥2|S|\geq 2, let λG(S)\lambda_G(S) be the maximum number of edge-disjoint SS-Steiner trees in GG, and define λk(G)\lambda_k(G) as the minimum of λG(S)\lambda_G(S) over all kk-subsets SS of V(G)V(G). Similarly, let κk(L(G))\kappa_k(L(G)) denote the minimum, over all kk-subsets of V(L(G))V(L(G)), of the maximum number of internally disjoint Steiner trees joining that subset. Li, Wu, Meng and Ma's conjecture. For every integer k≥2k\geq 2, if GG is connected and has at least kk vertices and at least kk edges, then

κk(L(G))≥λk(G).\kappa_k(L(G))\geq \lambda_k(G).

The conjecture would give a sharp relationship between generalized vertex-connectivity of a line graph and generalized edge-connectivity of the original graph. It is known for k=2k=2, k=3k=3, and k=4k=4, while the general case is presented as an open conjecture.

References

Primary source

Shasha Li, “k-tree connectivity of line graphs”, arXiv:2003.03568 (2020).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.