Kernel Set Problem and its Computation
Qi‐Wei Ge, Mitsuru Nakata · 2012
Given with a graph G and its any isomorphic graph Gâ², a minimum determiner set of G is a minimum set of vertices such that, if these vertices are assigned in one-to-one correspondence between G and Gâ² then correspondences of the remaining vertices of G are uniquely determined. A kernel set is a minimum determiner set with the least number of elements. In this paper, we i¬rstly dei¬ne determiner set and minimum determiner set properly as well as kernel set. Then we show the related properties and propose algorithms to i¬nd minimum determiner set as a previous step toward i¬nding kernel set. Finally, we give an example by applying proposed algorithms to show the usefulness of minimum determiner set as well as kernel set.