The (vertex-)monochromatic index of a graph (Q2012896)

Let \(G\) be an edge colored graph, let \(k\) be an integer such that \(2\leq k\leq |V(G)|\) and let \(S\) be a subset of \(V(G)\) of cardinality \(k\). A monochromatic \(S\)-tree is a tree that contains all vertices of \(S\) and all edges of \(T\) are of the same color. The \(k\)-monochromatic index \(\mathrm{mx}_k(G)\) of \(G\) is the maximum number of colors, such that for each \(S\) there exists a monochromatic \(S\)-tree. This invariant is a generalization of monochromatic connection number \(\mathrm{mc}(G)\) with the connection \(\mathrm{mc}(G)=\mathrm{mx}_2(G)\). In the first part of present work, authors prove that \(\mathrm{mx}_k(G)=|E(G)|-|V(G)|+2\) for each \(k\geq 3\) and any connected graph \(G\). The second part is devoted to \(k\)-monochromatic vertex index \(\mathrm{mvx}_k(G)\) of a graph \(G\). The difference in the definitions is that we observe vertex colored graphs and all inner vertices of a monochromatic \(S\)-tree have the same color. This problem is much harder as it is a NP-complete problem for every \(k\), \(2\leq k\leq |V(G)|\), to decide whether \(\mathrm{mvx}_k(G)\geq \ell\) where \(\ell\leq |V(G)|\), as presented by the authors.