2016/03/17 by Xueliang Li, Di Wu, Li, Xueliang +1
Mathematics · #05C15 #05C40 #68Q17 #68Q25 #68R10 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C15 #msc:05C40 #msc:68Q17 #msc:68Q25 #msc:68R10
paper · pdf · doi:10.48550/arxiv.1603.05338
13 pages
arxiv created 2016/03/19 · arxiv updated 2016/03/22
A tree T in an edge-colored graph H is called a monochromatic tree if all the edges of T have the same color. For S⊆ V(H), a monochromatic S-tree in H is a monochromatic tree of H containing the vertices of S. For a connected graph G and a given integer k with 2≤ k≤ |V(G)|, the k-monochromatic index mxk(G) of G is the maximum number of colors needed such that for each subset S⊆ V(G) of k vertices, there exists a monochromatic S-tree. In this paper, we prove that for any connected graph G, mxk(G)=|E(G)|-|V(G)|+2 for each k such that 3≤ k≤ |V(G)|. A tree T in a vertex-colored graph H is called a vertex-monochromatic tree if all the internal vertices of T have the same color. For S⊆ V(H), a vertex-monochromatic S-tree in H is a vertex-monochromatic tree of H containing the vertices of S. For a connected graph G and a given integer k with 2≤ k≤ |V(G)|, the k-monochromatic vertex-index mvxk(G) of G is the maximum number of colors needed such that for each subset S⊆ V(G) of k vertices, there exists a vertex-monochromatic S-tree. We show that for a given a connected graph G, and a positive integer L with L≤ |V(G)|, to decide whether mvxk(G)≥ L is NP-complete for each integer k such that 2≤ k≤ |V(G)|. We also obtain some Nordhaus-Gaddum-type results for the k-monochromatic vertex-index.