The (vertex-)monochromatic index of a graph

DOI10.1007/S10878-016-0048-2MaRDI QIDQ2012896zbMATHOpenAlexFDO

Authors Di Wu, Xueliang Li

Publication date 3 August 2017

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 5015716 (Why is no real title available?)
• scientific article; zbMATH DE number 4008449 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Colorful monochromatic connectivity
• Erdős-Gallai-type results for colorful monochromatic connectivity of a graph
• Graph theory with applications
• Nordhaus-Gaddum inequalities for domination in graphs
• Nordhaus-Gaddum-type theorem for rainbow connection number of graphs
• On Complementary Graphs
• On rainbow connection
• Rainbow connection in graphs
• Some extremal results on the colorful monochromatic vertex-connectivity of a graph
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree

Cited in

(7)

• Monochromatic \(k\)-edge-connection colorings of graphs
• Extremal graphs with maximum monochromatic connectivity
• Rainbow and monochromatic vertex-connection of random graphs
• Hardness results for three kinds of colored connections of graphs
• scientific article; zbMATH DE number 4041942 (Why is no real title available?)
• The monochromatic connectivity of graphs
• Further results on the total monochromatic connectivity of 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)