Li, Wu, Meng and Ma's -tree connectivity conjecture for line graphs
Li, Wu, Meng and Ma's -tree connectivity conjecture for line graphs
Let be a connected graph with at least vertices and at least edges, and let be its line graph. For a set with , let be the maximum number of edge-disjoint -Steiner trees in , and define as the minimum of over all -subsets of . Similarly, let denote the minimum, over all -subsets of , of the maximum number of internally disjoint Steiner trees joining that subset. Li, Wu, Meng and Ma's conjecture. For every integer , if is connected and has at least vertices and at least edges, then
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 , , and , 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
Sign in to submit a solution.
No solutions have been posted yet.