2016/06/13 by Hong Chang, Chang, Hong, Xueliang Li +5
Computer Science · Mathematics · #05C15 #05C40 #05C80 #05D40 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.1606.03872
openalex publication_date 2016/06/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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≤ k ≤ n. For S⊆ V(G) and |S| ≥ 2, an S-tree is a tree containing the vertices of S in G. Suppose \T1,T2,…,T_ℓ\ is a set of S-trees, they are called internally disjoint if E(Ti)∩ E(Tj)=∅ and V(Ti)∩ V(Tj)=S for 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 κ(S). The κ-connectivity κk(G) of G is defined by κk(G)=min\κ(S)| S is a k-subset of V(G)\. For a connected graph G of order n and for two integers k and ℓ with 2≤ k≤ n and 1≤ ℓ ≤ κk(G), the \emph(k,ℓ)-proper index pxk,ℓ(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 ℓ internally disjoint proper S-trees connecting them. In this paper, we show that for every pair of positive integers k and ℓ with k ≥ 3, there exists a positive integer N1=N1(k,ℓ) such that pxk,ℓ(Kn) = 2 for every integer n ≥ N1, and also there exists a positive integer N2=N2(k,ℓ) such that pxk,ℓ(Km,n) = 2 for every integer n ≥ N2 and m=O(nr) (r ≥ 1). In addition, we show that for every p ≥ c√[k](loga n)/(n) (c ≥ 5), pxk,ℓ(Gn,p)≤ 2 holds almost surely, where Gn,p is the Erdös-Rényi random graph model.