Kayal and Nezhmetdinov introduced in [Factoring groups efficiently, Int. Colloquium on Automata, Languages, and Programming (Springer, Berlin, Heidelberg, 2009), pp. 585–596] the concept of an irreducible conjugacy class and defined, for any finite non-abelian group, a simple graph on the set of all such classes. This graph is a key ingredient in their proposed algorithm for solving the group decomposition problem. This paper considers the class of finite groups for which the KN-graph is complete (KN-complete groups). The main result is a necessary and sufficient condition for a given group to be KN-complete, formulated in terms of its minimal non-central normal subgroups. This condition is used to obtain a more detailed description of the rather rich class of KN-complete groups.