We have investigated the formation of C-N bonds from individual atoms and single hydrogenated moieties on a series of transition metals. These reactions play a role in HCN formation at high oxygen coverage, also known as Andrussow oxidation, and they are fundamental to understand the ability of other materials to form part of alloys where Pt is the major component. Dehydrogenations take place quite easily under these high oxygen conditions and thus, the C+N, HC+N, and N+CH recombinations to form HCN or its isomer CNH might represent the rate-limiting steps for the reaction. For all the metals in the present study we have found that the activation energy for the reactions between H(x)C and NH(y) (x,y = 0,1) involved in C-N formation follow a linear relationship with the adsorption energy of the N atom. This is due to the common nature of all these transition states, where N-containing fragments get activated from three-fold hollow sites to bridge positions. The slopes of the linear dependence, though, depend on the valence of the N fragment, i.e., smaller slopes are found for NH moieties with respect to N ones.