标题： 关于图的完全单色连通性更多内容 显示英文标题

标题： More on total monochromatic connection of graphs

摘要： 一个图被称为 {\it 总颜色}，如果图的所有边和顶点都被着色。 图的一个全着色称为 {\it 单色连通着色}（简称 {\it TMC-着色}），如果图中任意两个顶点由一条路径连接，该路径上的边和内部顶点具有相同的颜色。 对于一个连通图 $G$， {\it 总单色连接数}（记作 $tmc(G)$）被定义为在 $G$的TMC-着色中使用的最大颜色数。 注意，如果 $G$ 不连通，则不存在 TMC-着色法，在这种情况下我们简单地令 $tmc(G)=0$。 本文首先刻画了阶数为 $n$、大小为 $m$ 且分别具有 $tmc(G)=3,4,5,6,m+n-2,m+n-3$ 和 $m+n-4$ 的所有图。 然后我们确定随机图具有 $tmc(G)\geq f(n)$ 的阈值函数，其中 $f(n)$ 是满足 $1\leq f(n)<\frac{1}{2}n(n-1)+n$ 的函数。 最后，我们证明对于给定的连通图 $G$ 和正整数 $L$，当 $L\leq m+n$ 时，判定 $tmc(G)\geq L$ 是否成立是 NP 完全问题。 显示英文摘要

摘要： A graph is said to be {\it total-colored} if all the edges and the vertices of the graph are colored. 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 path whose edges and internal vertices on the path have the same color. 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$. Note that a TMC-coloring does not exist if $G$ is not connected, in which case we simply let $tmc(G)=0$. In this paper, we first characterize all graphs of order $n$ and size $m$ with $tmc(G)=3,4,5,6,m+n-2,m+n-3$ and $m+n-4$, respectively. Then we determine the threshold function for a random graph to have $tmc(G)\geq f(n)$, where $f(n)$ is a function satisfying $1\leq f(n)<\frac{1}{2}n(n-1)+n$. Finally, we show that for a given connected graph $G$, and a positive integer $L$ with $L\leq m+n$, it is NP-complete to decide whether $tmc(G)\geq L$.