The search functionality is under construction.

The search functionality is under construction.

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

Takafumi GOTO

Yamaguchi University

Koki TANAKA

Yamaguchi University

Mitsuru NAKATA

Yamaguchi University

Qi-Wei GE

Yamaguchi University

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.

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 -