The \(\kappa_k\)-connectivity of line graphs (Q2197398): Difference between revisions

For a subset \(S\) of the vertex set of a graph \(G\) with \(|S|\geq 2\), let \(\kappa_{G}(S)\) (\(\lambda_{G}(S)\)) denote the maximum number of internally disjoint (edge-disjoint) trees of \(G\) such that each pair of these trees has exactly \(S\) in common. The generalized \(k\)-connectivity (\(k\)-edge-connectivity) of \(G\) is defined as \(\kappa_{k}(G)=\min\{\kappa_{G}(S) \mid S \subseteq V(G) \text{ and } |S|=k\}\) (\(\lambda_{k}(G)=\min\{\lambda_{G}(S)\mid S \subseteq V(G) \text{ and } |S|=k\}\)). Let \(L(G)\) denote the line graph of \(G\). The relation between \(\kappa_{k}(L(G))\) and \(\lambda_{k}(G)\) is investigated and it is shown that \[\kappa_{k}(L(G))\geq \lambda_{k}(G)-\Bigm\lceil{\frac{\lceil{\frac{\operatorname{mad}(G)}{2}\rceil}}{2}}\Bigm\rceil, \] where \(\operatorname{mad}(G)\) is the maximum average degree of \(G\), \(\kappa_{k}(L(G))\geq \lambda_{k}(G)-\Bigm\lceil{\frac{\lfloor{\frac{r}{2}\rfloor}}{2}}\Bigm\rceil\) for any integers \(k\) and \(r\) with \(k\leq \binom{r}{2}\) and the conjecture \(\kappa_{k}(L(G))\geq \lambda_{k}(G)\) holds for three cases: \(k=5\), \(G\) is the wheel graph and \(G\) is the complete bipartite graph \(K_{3,n}\).