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

A tree T in an edge-colored graph is called a 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$$ 2 ≤ k ≤ n . For $$S\subseteq V(G)$$ S ⊆ V ( G ) and $$|S| \ge 2$$ | S | ≥ 2 , an S-tree is a tree containing the vertices of S in G. A set $$\{T_1,T_2,\ldots ,T_\ell \}$$ { T 1 , T 2 , … , T ℓ } of S-trees is called internally disjoint if $$E(T_i)\cap E(T_j)=\emptyset $$ E ( T i ) ∩ E ( T j ) = ∅ and $$V(T_i)\cap V(T_j)=S$$ V ( T i ) ∩ V ( T j ) = S for $$1\le i\ne j\le \ell $$ 1 ≤ i ≠ j ≤ ℓ . For a set S of k vertices of G, the maximum number of internally disjoint S-trees in G is denoted by $$\kappa (S)$$ κ ( S ) . The k-connectivity $$\kappa _k(G)$$ κ k ( G ) of G is defined by $$\kappa _k(G)=\min \{\kappa (S)\mid S$$ κ k ( G ) = min { κ ( S ) ∣ S is a k-subset of $$V(G)\}$$ V ( G ) } . For a connected graph G of order n and for two integers k and $$\ell $$ ℓ with $$2\le k\le n$$ 2 ≤ k ≤ n and $$1\le \ell \le \kappa _k(G)$$ 1 ≤ ℓ ≤ κ k ( G ) , the $$(k,\ell )$$ ( k , ℓ ) -proper index $$px_{k,\ell }(G)$$ p x k , ℓ ( G ) of G is the minimum number of colors that are required 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$$ k ≥ 3 and $$\ell \le \kappa _k(K_{n,n})$$ ℓ ≤ κ k ( K n , n ) , there exists a positive integer $$N_1=N_1(k,\ell )$$ N 1 = N 1 ( k , ℓ ) such that $$px_{k,\ell }(K_n) = 2$$ p x k , ℓ ( K n ) = 2 for every integer $$n \ge N_1$$ n ≥ N 1 , and there exists also a positive integer $$N_2=N_2(k,\ell )$$ N 2 = N 2 ( k , ℓ ) such that $$px_{k,\ell }(K_{m,n}) = 2$$ p x k , ℓ ( K m , n ) = 2 for every integer $$n \ge N_2$$ n ≥ N 2 and $$m=O(n^r) (r \ge 1)$$ m = O ( n r ) ( r ≥ 1 ) . In addition, we show that for every $$p \ge c\root k \of {\frac{\log _a n}{n}}$$ p ≥ c log a n n k ( $$c \ge 5$$ c ≥ 5 ), $$px_{k,\ell }(G_{n,p})\le 2$$ p x k , ℓ ( G n , p ) ≤ 2 holds almost surely, where $$G_{n,p}$$ G n , p is the Erdős–Rényi random graph model.