| Presentation | 2018-01-18 Verification of an Approach to Find Determiner Set of Graphs Koki Tanaka, Takafumi Goto, Mituru Nakata, Chiranut Sa-ngiamsak, Qi-Wei Ge, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | An automorphism of graph G=(V,E) is such a one-to-one correspondence from the vertex set V to itself that adjacency of the vertices are maintained. In general, there are multiple automorphisms for a graph. When a one-to-one correspondence of a subset S of V is decided and meanwhile the adjacency relationship of S is maintained, S is called determiner set of G if the correspondence of all the vertices in V-S is uniquely determined.Also, if no any proper subset of a determiner set S is a determiner set, S is called minimum determiner set. Furthermore, a determiner set S with the smallest number of elements is called a kernel set. In this paper, we verify the restriction of the algorithm to determine whether a given node set is a determiner set. First, definitions and properties related to determiner sets are given. Then our method of judging determiner sets as well as its experimental results are explained. Finally, the discussion is done for the definitions related to symmetric nodes. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | graph / automorphism / determiner set / minimum determiner set / kernel set / symmetric node |
| Paper # | MSS2017-51,SS2017-38 |
| Date of Issue | 2018-01-11 (MSS, SS) |
| Conference Information | |
| Committee | SS / MSS |
|---|---|
| Conference Date | 2018/1/18(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Kazuhiro Ogata(JAIST) / Morikazu Nakamura(Univ. of Ryukyus) |
| Vice Chair | Akio Nakata(Hiroshima City Univ.) / Shigemasa Takai(Osaka Univ.) |
| Secretary | Akio Nakata(Tokyo Inst. of Tech.) / Shigemasa Takai(Osaka Univ.) |
| Assistant | Kazuyuki Shima(Hiroshima City Univ.) / Hideki Kinjo(Okinawa Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Software Science / Technical Committee on Mathematical Systems Science and its applications |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Verification of an Approach to Find Determiner Set of Graphs |
| Sub Title (in English) | |
| Keyword(1) | graph |
| Keyword(2) | automorphism |
| Keyword(3) | determiner set |
| Keyword(4) | minimum determiner set |
| Keyword(5) | kernel set |
| Keyword(6) | symmetric node |
| 1st Author's Name | Koki Tanaka |
| 1st Author's Affiliation | Yamaguchi University(Yamaguchi Univ.) |
| 2nd Author's Name | Takafumi Goto |
| 2nd Author's Affiliation | Yamaguchi University(Yamaguchi Univ.) |
| 3rd Author's Name | Mituru Nakata |
| 3rd Author's Affiliation | Yamaguchi University(Yamaguchi Univ.) |
| 4th Author's Name | Chiranut Sa-ngiamsak |
| 4th Author's Affiliation | Khon Kaen University(Khon Kaen Univ.) |
| 5th Author's Name | Qi-Wei Ge |
| 5th Author's Affiliation | Yamaguchi University(Yamaguchi Univ.) |
| Date | 2018-01-18 |
| Paper # | MSS2017-51,SS2017-38 |
| Volume (vol) | vol.117 |
| Number (no) | MSS-380,SS-381 |
| Page | pp.pp.25-30(MSS), pp.25-30(SS), |
| #Pages | 6 |
| Date of Issue | 2018-01-11 (MSS, SS) |