کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4646570 | 1413648 | 2017 | 6 صفحه PDF | دانلود رایگان |
A graph is said to be total-colored if all the edges and the vertices of the graph are colored. A path in a total-colored graph is a 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 total monochromatically-connecting coloring (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 GG, the total monochromatic connection number , denoted by tmc(G)tmc(G), is defined as the maximum number of colors used in a TMC-coloring of GG. These concepts are inspired by the concepts of monochromatic connection number mc(G)mc(G), monochromatic vertex connection number mvc(G)mvc(G) and total rainbow connection number trc(G)trc(G) of a connected graph GG. Let l(T)l(T) denote the number of leaves of a tree TT, and let l(G)=max{l(T)|T is a spanning tree ofG} for a connected graph GG. In this paper, we show that there are many graphs GG such that tmc(G)=m−n+2+l(G)tmc(G)=m−n+2+l(G), and moreover, we prove that for almost all graphs GG, tmc(G)=m−n+2+l(G)tmc(G)=m−n+2+l(G) holds. Furthermore, we compare tmc(G)tmc(G) with mvc(G)mvc(G) and mc(G)mc(G), respectively, and obtain that there exist graphs GG such that tmc(G)tmc(G) is not less than mvc(G)mvc(G) and vice versa, and that tmc(G)=mc(G)+l(G)tmc(G)=mc(G)+l(G) holds for almost all graphs. Finally, we prove that tmc(G)≤mc(G)+mvc(G)tmc(G)≤mc(G)+mvc(G), and the equality holds if and only if GG is a complete graph.
Journal: Discrete Mathematics - Volume 340, Issue 2, 6 February 2017, Pages 175–180