Detectable colorings of graphs

Abstract

Let G be a connected graph of order n ≥ 3 and let c: E(G) → {1,2, . . . ,k} be a coloring of the edges of G (where adjacent edges may be colored the same). For each vertex v of G, the color code of v is the fc-tuple c(v) = (a₁, a₂, ⋯, a_k), where a_i is the number of edges incident with v that are colored i (1 ≤ i ≤ k). The coloring c is called detectable if distinct vertices have distinct color codes; while the detection number det((G) of G is the minimum positive integer k for which G has a detectable k-coloring. The detection numbers of cycles, complete graphs, and complete bipartite graphs are determined. It is shown that a pair k,n of positive integers is realizable as the detection number and the order of some nontrivial connected graph if and only if k = n = 3 or 2 ≤ k ≤ n - 1.