2020/03/07 by Li, Shasha
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2003.03568
For a graph G=(V,E) and a set S⊆ V(G) of size at least 2, an S-Steiner tree T is a subgraph of G that is a tree with S⊆ V(T). Two S-Steiner trees T and T' are internally disjoint (resp. edge-disjoint) if E(T)∩ E(T')=∅ and V(T)∩ V(T')=S (resp. if E(T)∩ E(T')=∅). Let κG (S) (resp. λG (S)) denote the maximum number of internally disjoint (resp. edge-disjoint) S-Steiner trees in G. The k-tree connectivity κk(G) (resp. k-tree edge-connectivity λk(G)) of G is then defined as the minimum κG (S) (resp. λG (S)), where S ranges over all k-subsets of V(G). In [H. Li, B. Wu, J. Meng, Y. Ma, Steiner tree packing number and tree connectivity, Discrete Math. 341(2018), 1945--1951], the authors conjectured that if a connected graph G has at least k vertices and at least k edges, then κk(L(G))≥ λk(G) for any k≥ 2, where L(G) is the line graph of G. In this paper, we confirm this conjecture and prove that the bound is sharp.