Rainbow Trees in Small Cubic Graphs

Abstract

Let $G$ be a nontrivial connected graph of order $n$ and $k$ an integer with $2\le k\le n$. For a set $S$ of $k$ vertices of $G$, let $\kappa (S)$ denote the maximum number $\ell$ of pairwise edge-disjoint trees $T_1,T_2,\dots ,T_{\ell }$ in $G$ such that $V(T_i)\cap V(T_j)=S$ for every pair $i,j$ of distinct integers with $1\le i,j\le \ell$. A collection $\{T_1,T_2,\dots ,T_{\ell }\}$ of trees in $G$ with this property is called a set of internally disjoint trees connecting $S$. The $k$-connectivity ${\kappa }_k(G)$ of $G$ is defined as ${\kappa }_k(G)=\text{min}\{\kappa (S)\}$, where the minimum is taken over all $k$-element subsets $S$ of $V(G)$. Thus ${\kappa }_2(G)$ is the connectivity $\kappa (G)$ of $G$. In an edge-colored graph $G$ in which adjacent edges may be colored the same, a tree $T$ is a rainbow tree in $G$ if no two edges of $T$ are colored the same. For each integer $\ell$ with $1\le \ell \le {\kappa }_k(G)$, a $(k,\ell )$-rainbow coloring of $G$ is an edge coloring of $G$ (in which adjacent