The (vertex-)monochromatic index of a graph

Xueliang Li () and Di Wu ()
Additional contact information
Xueliang Li: Nankai University
Di Wu: Nankai University

Journal of Combinatorial Optimization, 2017, vol. 33, issue 4, No 17, 1443-1453

Abstract: 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)$$ S ⊆ 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)|$$ 2 ≤ k ≤ | V ( G ) | , the k -monochromatic index $$mx_k(G)$$ m x k ( G ) (k -monochromatic vertex-index $$mvx_k(G)$$ m v x k ( G ) ) of G is the maximum number of colors needed such that for each subset $$S\subseteq V(G)$$ S ⊆ V ( G ) of k vertices, there exists a monochromatic (vertex-monochromatic) S-tree. For $$k=2$$ k = 2 , Caro and Yuster showed that $$mc(G)=mx_2(G)=|E(G)|-|V(G)|+2$$ m c ( G ) = m x 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$$ k ≥ 3 , $$mx_k(G)=|E(G)|-|V(G)|+2$$ m x 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)$$ m v x 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)|$$ L ≤ | V ( G ) | , to decide whether $$mvx_k(G)\ge L$$ m v x k ( G ) ≥ L is NP-complete for each integer k such that $$2\le k\le |V(G)|$$ 2 ≤ k ≤ | V ( G ) | . Finally, we obtain some Nordhaus–Gaddum-type results for the k-monochromatic vertex-index.

Keywords: k-Monochromatic index; k-Monochromatic vertex-index; NP-complete; Nordhaus–Gaddum-type result; 05C15; 05C40; 68Q17; 68Q25; 68R10 (search for similar items in EconPapers)
Date: 2017
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-016-0048-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:33:y:2017:i:4:d:10.1007_s10878-016-0048-2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-016-0048-2

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().