$k$-tree connectivity of line graphs

Abstract

For a graph $G=(V,E)$ and a set $S\subseteq V(G)$ of size at least $2$, an $S$-Steiner tree $T$ is a subgraph of $G$ that is a tree with $S\subseteq V(T)$. Two $S$-Steiner trees $T$ and $T^{\prime }$ are internally disjoint (resp. edge-disjoint) if $E(T)\cap E(T^{\prime })=\varnothing$ and $V(T)\cap V(T^{\prime })=S$ (resp. if $E(T)\cap E(T^{\prime })=\varnothing$). Let ${\kappa }_G(S)$ (resp. ${\lambda }_G(S)$) denote the maximum number of internally disjoint (resp. edge-disjoint) $S$-Steiner trees in $G$. The $k$-tree connectivity ${\kappa }_k(G)$ (resp. $k$-tree edge-connectivity ${\lambda }_k(G)$) of $G$ is then defined as the minimum ${\kappa }_G(S)$ (resp. ${\lambda }_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 ${\kappa }_k(L(G))\ge {\lambda }_k(G)$ for any $k\ge 2$, where $L(G)$ is the line graph of $G$. In this paper, we confirm this conjecture and prove that the bound is sharp.

References in corpus (1)

• On the generalized (edge-)connectivity of graphs