The Total Detection Numbers of Graphs

Let \( G \) be a connected graph of size at least 2 and \( c: E(G) \to \{0, 1, \ldots, 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, \ldots, a_{k-1}) \), where \( a_i \) is the number of edges incident with \( v \) that are labeled \( i \) (for \( 0 \leq i \leq 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 \geq 2 \), then \( 1 \leq \text{td}(G) \leq \binom{m}{2} \). We present characterizations of all connected graphs \( G \) of size \( m \geq 2 \) for which \( \text{td}(G) \in \{1, \binom{m}{2}\} \). The total detection numbers of complete graphs and cycles are also investigated.