2015/05/06 by Yaping Mao, Zhao Wang, Mao, Yaping +5 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Graph Labeling and Dimension Problems #math.CO
paper · pdf · doi:10.48550/arxiv.1505.01424
18 pages, 2 figures. arXiv admin note: text overlap with arXiv:1412.7798 by other authors
arxiv created 2015/05/06 · openalex publication_date 2015/05/06 · arxiv updated 2015/05/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The concept of monochromatic connectivity was introduced by Caro and Yuster. A path in an edge-colored graph is called a monochromatic path if all the edges on the path are colored the same. An edge-coloring of G is a monochromatic connection coloring (MC-coloring, for short) if there is a monochromatic path joining any two vertices in G. The monochromatic connection number, denoted by mc(G), is defined to be the maximum number of colors used in an MC-coloring of a graph G. In this paper, we study the monochromatic connection number on the lexicographical, strong, Cartesian and direct product and present several upper and lower bounds for these products of graphs.