Abstract
A tree T in an edge-colored (vertex-colored) graph H is called a monochromatic (vertex-monochromatic) tree if all the edges (internal vertices) of T have the same color. For \(S\subseteq V(H)\), a monochromatic (vertex-monochromatic) S-tree in H is a monochromatic (vertex-monochromatic) tree of H containing the vertices of S. For a connected graph G and a given integer k with \(2\le k\le |V(G)|\), the k -monochromatic index \(mx_k(G)\) (k -monochromatic vertex-index \(mvx_k(G)\)) of G is the maximum number of colors needed such that for each subset \(S\subseteq V(G)\) of k vertices, there exists a monochromatic (vertex-monochromatic) S-tree. For \(k=2\), Caro and Yuster showed that \(mc(G)=mx_2(G)=|E(G)|-|V(G)|+2\) for many graphs, but it is not true in general. In this paper, we show that for \(k\ge 3\), \(mx_k(G)=|E(G)|-|V(G)|+2\) holds for any connected graph G, completely determining the value. However, for the vertex-version \(mvx_k(G)\) things will change tremendously. We show that for a given connected graph G, and a positive integer L with \(L\le |V(G)|\), to decide whether \(mvx_k(G)\ge L\) is NP-complete for each integer k such that \(2\le k\le |V(G)|\). Finally, we obtain some Nordhaus–Gaddum-type results for the k-monochromatic vertex-index.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bondy JA, Murty USR (1976) Graph theory with applications. The Macmillan Press, London
Cai Q, Li X, Wu D (2015a) Erdös–Gallai-type results for colorful monochromatic connectivity of a graph. J Comb Optim. doi:10.1007/s10878-015-9938-y, in press
Cai Q, Li X, Wu D (2015b) Some extremal results on the colorful monochromatic vertex-connectivity of a graph. arXiv:1503.08941
Caro Y, Lev A, Roditty Y, Tuza Z, Yuster R (2008) On rainbow connection. Electron J Combin 15(1):R57
Caro Y, Yuster R (2011) Colorful monochromatic connectivity. Discrete Math 311:1786–1792
Chartrand G, Johns G, McKeon K, Zhang P (2008) Rainbow connection in graphs. Math Bohem 133:85–98
Chen L, Li X, Lian H (2013) Nordhaus–Gaddum-type theorem for rainbow connection number of graphs. Graphs Combin 29:1235–1247
Garey MR, Johnson DS (1979) Computers and intractability. Freeman, New York
Harary F, Haynes TW (1996) Nordhaus–Gaddum inequalities for domination in graphs. Discrete Math 155:99–105
Krivelevich M, Yuster R (2010) The rainbow connection of a graph is (at most) reciprocal to its minimum degree. J Graph Theory 63(3):185–191
Laskar R, Peters K (1985) Vertex and edge domination parameters in graphs. Congr Numer 48:291–305
Li X, Shi Y, Sun Y (2013) Rainbow connections of graphs: a survey. Graphs Combin 29:1–38
Li X, Sun Y (2012) Rainbow connections of graphs. Springer briefs in math. Springer, New York
Nordhaus EA, Gaddum JW (1956) On complementary graphs. Am Math Monthly 63:175–177
Zhang L, Wu B (2005) The Nordhaus–Gaddum-type inequalities of some chemical indices. MATCH Commun Math Comput Chem 54:189–194
Acknowledgments
Supported by NSFC No.11371205 and 11531011, “973” program No.2013CB834204, and PCSIRT.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Li, X., Wu, D. The (vertex-)monochromatic index of a graph. J Comb Optim 33, 1443–1453 (2017). https://doi.org/10.1007/s10878-016-0048-2
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-016-0048-2