
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Properties and Judgment of Determiner Sets
Takafumi GOTO Koki TANAKA Mitsuru NAKATA QiWei GE
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E102A
No.2
pp.365371 Publication Date: 2019/02/01
Online ISSN: 17451337
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>>
Summary:
An automorphism of a graph G=(V, E) is such a onetoone correspondence from vertex set V to itself that all the adjacencies of the vertices are maintained. Given a subset S of V whose onetoone correspondence is decided, if the vertices of VS 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.

