Detectable colorings of graphs - Chartrand, Gary; Escuadro, Henry; Okamoto, Futaba; Zhang, Ping (Utilitas Mathematica, 2006)
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) = (a1, a2, ⋯, ak), where ai 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.