The $(k,\ell )$-proper index of graphs

Abstract

A tree $T$ in an edge-colored graph is called a {\it proper tree} if no two adjacent edges of $T$ receive the same color. Let $G$ be a connected graph of order $n$ and $k$ be an integer with $2\le k\le n$. For $S\subseteq V(G)$ and $|S|\ge 2$, an $S$-tree is a tree containing the vertices of $S$ in $G$. Suppose $\{T_1,T_2,\dots ,T_{\ell }\}$ is a set of $S$-trees, they are called \emph{internally disjoint} if $E(T_i)\cap E(T_j)=\varnothing$ and $V(T_i)\cap V(T_j)=S$ for $1\le i\ne j\le \ell$. For a set $S$ of $k$ vertices of $G$, the maximum number of internally disjoint $S$-trees in $G$ is denoted by $\kappa (S)$. The $\kappa$-connectivity ${\kappa }_k(G)$ of $G$ is defined by ${\kappa }_k(G)=\min \{\kappa (S)\mid S$ is a $k$-subset of $V(G)\}$. For a connected graph $G$ of order $n$ and for two integers $k$ and $\ell$ with $2\le k\le n$ and $1\le \ell \le {\kappa }_k(G)$, the \emph{$(k,\ell )$-proper index $p{x}_{k,\ell }(G)$} of $G$ is the minimum number of colors that are needed in an edge-coloring of $G$ such that for every $k$-subset $S$ of $V(G)$, there exist $\ell$ internally disjoint proper $S$-trees connecting them. In this paper, we show that for every pair of positive integers $k$ and $\ell$ with $k\ge 3$, there exists a positive integer $N_1=N_1(k,\ell )$ such that $p{x}_{k,\ell }(K_n)=2$ for every integer $n\ge N_1$, and also there exists a positive integer $N_2=N_2(k,\ell )$ such that $p{x}_{k,\ell }(K_{m,n})=2$ for every integer $n\ge N_2$ and $m=O(n^r)(r\ge 1)$. In addition, we show that for every $p\ge c\sqrt[k]{\frac{{\log }_{a}n}{n}}$ ($c\ge 5$), $p{x}_{k,\ell }(G_{n,p})\le 2$ holds almost surely, where $G_{n,p}$ is the Erdös-Rényi random graph model.

14 pages