The k-proper index of graphs

摘要

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, we state some simple observations about pxk(G) for a nontrivial connected graph G. 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, we characterize the graphs with k-proper index n−1 and n−2, respectively.