2016/01/13 by Hui Jiang, Xueliang Li, Jiang, Hui +3 · 1 citation
Computer Science · Mathematics · #05C05 #05C15 #05C40 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #math.CO #msc:05C05 #msc:05C15 #msc:05C40
paper · pdf · doi:10.48550/arxiv.1601.03241
12 pages
arxiv created 2016/01/13 · openalex publication_date 2016/01/13 · arxiv updated 2016/01/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph is said to be \it total-colored if all the edges and the vertices of the graph are colored. A path in a total-colored graph is a \it total monochromatic path if all the edges and internal vertices on the path have the same color. A total-coloring of a graph is a \it total monochromatically-connecting coloring (\it TMC-coloring, for short) if any two vertices of the graph are connected by a total monochromatic path of the graph. For a connected graph G, the \it total monochromatic connection number, denoted by tmc(G), is defined as the maximum number of colors used in a TMC-coloring of G. These concepts are inspired by the concepts of monochromatic connection number mc(G), monochromatic vertex connection number mvc(G) and total rainbow connection number trc(G) of a connected graph G. Let l(T) denote the number of leaves of a tree T, and let l(G)=max\ l(T) | T is a spanning tree of G \ for a connected graph G. In this paper, we show that there are many graphs G such that tmc(G)=m-n+2+l(G), and moreover, we prove that for almost all graphs G, tmc(G)=m-n+2+l(G) holds. Furthermore, we compare tmc(G) with mvc(G) and mc(G), respectively, and obtain that there exist graphs G such that tmc(G) is not less than mvc(G) and vice versa, and that tmc(G)=mc(G)+l(G) holds for almost all graphs. Finally, we prove that tmc(G)≤ mc(G)+mvc(G), and the equality holds if and only if G is a complete graph.