The Total Detection Numbers of Graphs

Abstract

Let $G$ be a connected graph of size at least 2 and $c:E(G)\to \{0,1,\dots ,k-1\}$ an edge coloring (or labeling) of $G$ using $k$ colors (where adjacent edges may be assigned the same color). For each vertex $v$ of $G$, the color code of $v$ with respect to $c$ is the $k$-tuple $\text{code}(v)=(a_0,a_1,\dots ,a_{k-1})$, where $a_i$ is the number of edges incident with $v$ that are labeled $i$ (for $0\le i\le k-1$). The labeling $c$ is called a detectable labeling if distinct vertices in $G$ have distinct color codes. The value $\text{val}(c)$ of a detectable labeling $c$ of a graph $G$ is the sum of the colors assigned to the edges in $G$. The total detection number $\text{td}(G)$ of $G$ is defined by $\text{td}(G)=min\{\text{val}(c)\}$, where the minimum is taken over all detectable labelings $c$ of $G$. Thus, if $G$ is a connected graph of size $m\ge 2$, then $1\le \text{td}(G)\le (\genfrac{}{}{0ex}{}{m}{2})$. We present characterizations of all connected graphs $G$ of size $m\ge 2$ for which $\text{td}(G)\in \{1,(\genfrac{}{}{0ex}{}{m}{2})\}$. The total detection numbers of complete graphs and cycles are also investigated.