IEICE TRANSACTIONS on Fundamentals
Properties and Judgment of Determiner Sets
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E102-A No.2 pp.365-371
- Publication Date
- 2019/02/01
- Publicized
- 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
Authors
Takafumi GOTO
Yamaguchi University
Koki TANAKA
Yamaguchi University
Mitsuru NAKATA
Yamaguchi University
Qi-Wei GE
Yamaguchi University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Takafumi GOTO, Koki TANAKA, Mitsuru NAKATA, Qi-Wei GE, "Properties and Judgment of Determiner Sets" in IEICE TRANSACTIONS on Fundamentals,
vol. E102-A, no. 2, pp. 365-371, February 2019, doi: 10.1587/transfun.E102.A.365.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E102.A.365/_p
Copy
@ARTICLE{e102-a_2_365,
author={Takafumi GOTO, Koki TANAKA, Mitsuru NAKATA, Qi-Wei GE, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Properties and Judgment of Determiner Sets},
year={2019},
volume={E102-A},
number={2},
pages={365-371},
abstract={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.},
keywords={},
doi={10.1587/transfun.E102.A.365},
ISSN={1745-1337},
month={February},}
Copy
TY - JOUR
TI - Properties and Judgment of Determiner Sets
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 365
EP - 371
AU - Takafumi GOTO
AU - Koki TANAKA
AU - Mitsuru NAKATA
AU - Qi-Wei GE
PY - 2019
DO - 10.1587/transfun.E102.A.365
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E102-A
IS - 2
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - February 2019
AB - 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.
ER -
English
