Properties and Judgment of Determiner Sets

Takafumi GOTO  Koki TANAKA  Mitsuru NAKATA  Qi-Wei GE  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E102-A   No.2   pp.365-371
Publication Date: 2019/02/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E102.A.365
Type of Manuscript: Special Section PAPER (Special Section on Mathematical Systems Science and its Applications)
Category: 
Keyword: 
graph,  automorphism,  determiner set,  minimal determiner set,  kernel set,  

Full Text: PDF(1.3MB)>>
Buy this Article




Summary: 
An automorphism of a graph G=(V, E) is such a one-to-one correspondence from vertex set V to itself that all the adjacencies of the vertices are maintained. Given a subset S of V whose one-to-one correspondence is decided, if the vertices of V-S possess unique correspondence in all the automorphisms that satisfy the decided correspondence for S, S is called determiner set of G. Further, S is called minimal determiner set if no proper subset of S is a determiner set and called kernel set if determiner set S with the smallest number of elements. Moreover, a problem to judge whether or not S is a determiner set is called determiner set decision problem. The purpose of this research is to deal with determiner set decision problem. In this paper, we firstly give the definitions and properties related to determiner sets and then propose an algorithm JDS that judges whether a given S is a determiner set of G in polynomial computation time. Finally, we evaluate the proposed algorithm JDS by applying it to possibly find minimal determiner sets for 100 randomly generated graphs. As the result, all the obtained determiner sets are minimal, which implies JDS is a reasonably effective algorithm for the judgement of determiner sets.