The k-proper index of graphs

الأصل · EN

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 pxₖ(G), is the smallest number of colors needed in a k-proper coloring of G. In this paper, some simple observations about pxₖ(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 pxₖ(G)=a and rxₖ(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.