The (vertex-)monochromatic index of a graph

DOI10.1007/S10878-016-0048-2zbMATH Open1379.05038arXiv1603.05338OpenAlexW2298472417MaRDI QIDQ2012896FDOQ2012896

Authors: Di Wu, Xueliang Li 

Publication date: 3 August 2017

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Abstract: A tree $T$ in an edge-colored graph $H$ is called a emph{monochromatic tree} if all the edges of $T$ have the same color. For $SsubseteqV(H)$, a emph{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 $2leqkleq|V(G)|$, the emph{$k$-monochromatic index $m{x}_k(G)$} of $G$ is the maximum number of colors needed such that for each subset $SsubseteqV(G)$ of $k$ vertices, there exists a monochromatic $S$-tree. In this paper, we prove that for any connected graph $G$, $m{x}_k(G)=|E(G)|-|V(G)|+2$ for each $k$ such that $3leqkleq|V(G)|$. A tree $T$ in a vertex-colored graph $H$ is called a emph{vertex-monochromatic tree} if all the internal vertices of $T$ have the same color. For $SsubseteqV(H)$, a emph{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 $2leqkleq|V(G)|$, the emph{$k$-monochromatic vertex-index $mv{x}_k(G)$} of $G$ is the maximum number of colors needed such that for each subset $SsubseteqV(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 $Lleq|V(G)|$, to decide whether $mv{x}_k(G)geqL$ is NP-complete for each integer $k$ such that $2leqkleq|V(G)|$. We also obtain some Nordhaus-Gaddum-type results for the $k$-monochromatic vertex-index.

Full work available at URL: https://arxiv.org/abs/1603.05338

Recommendations

• Some extremal results on the colorful monochromatic vertex-connectivity of a graph
• Note on the vertex-rainbow index of a graph
• Some results on the 3-vertex-rainbow index of a graph
• scientific article; zbMATH DE number 4041942
• Colorful monochromatic connectivity

zbMATH Keywords

NP-complete problemmonochromatic tree\(k\)-monochromatic index\(k\)-monochromatic vertex index

Mathematics Subject Classification ID

Trees (05C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Cites Work

• Title not available (Why is that?)
• On rainbow connection
• Rainbow connections of graphs
• Graph theory with applications
• Rainbow connection in graphs
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree
• On Complementary Graphs
• Nordhaus-Gaddum-type theorem for rainbow connection number of graphs
• Title not available (Why is that?)
• Nordhaus-Gaddum inequalities for domination in graphs
• Some extremal results on the colorful monochromatic vertex-connectivity of a graph
• Colorful monochromatic connectivity
• Erdős-Gallai-type results for colorful monochromatic connectivity of a graph
• Title not available (Why is that?)

Cited In (7)

• The monochromatic connectivity of graphs
• Title not available (Why is that?)
• Monochromatic \(k\)-edge-connection colorings of graphs
• Further results on the total monochromatic connectivity of graphs
• Extremal graphs with maximum monochromatic connectivity
• Hardness results for three kinds of colored connections of graphs
• Rainbow and monochromatic vertex-connection of random graphs

This page was built for publication: The (vertex-)monochromatic index of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2012896)