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

From papers

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 SV(G)S\subseteq V(G) with S2|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 k2k\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.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.