2016/01/14 by Lin Chen, Xueliang Li, Chen, Lin +3
Mathematics · #05C05 #05C15 #05C40 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C05 #msc:05C15 #msc:05C40
paper · pdf · doi:10.48550/arxiv.1601.03503
12 pages
arxiv created 2016/01/14 · arxiv updated 2016/01/15
A tree T in an edge-colored graph is a proper tree if any two adjacent edges of T are colored with different colors. Let G be a graph of order n and k be a fixed integer with 2≤ k≤ n. For a vertex set S⊆ V(G), a tree containing the vertices of S in G is called an S-tree. An edge-coloring of G is called a k-proper coloring if for every set S of k vertices in G, there exists a proper S-tree in G. The k-proper index of a nontrivial connected graph G, denoted by pxk(G), is the smallest number of colors needed in a k-proper coloring of G. In this paper, some simple observations about pxk(G) for a nontrivial connected graph G are stated. Meanwhile, the k-proper indices of some special graphs are determined, and for every pair of positive integers a, b with 2≤ a≤ b, a connected graph G with pxk(G)=a and rxk(G)=b is constructed for each integer k with 3≤ k≤ n. Also, the graphs with k-proper index n-1 and n-2 are respectively characterized.