Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2508.07615 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915447923802112 |
|---|---|
| author | Hu, Chuanfu Hou, Aimin |
| author_facet | Hu, Chuanfu Hou, Aimin |
| contents | The criteria for determining graph isomorphism are crucial for solving graph isomorphism problems. The necessary condition is that two isomorphic graphs possess invariants, but their function can only be used to filtrate and subdivide candidate spaces. The sufficient conditions are used to rebuild the isomorphic reconstruction of special graphs, but their drawback is that the isomorphic functions of subgraphs may not form part of the isomorphic functions of the parent graph. The use of sufficient or necessary conditions generally results in backtracking to ensure the correctness of the decision algorithm. The sufficient and necessary conditions can ensure that the determination of graph isomorphism does not require backtracking, but the correctness of its proof process is difficult to guarantee. This article proposes a verification method that can correctly determine whether the judgment conditions proposed by previous researchers are sufficient and necessary conditions. A subdivision method has also been proposed in this article, which can obtain more subdivisions for necessary conditions and effectively reduce the size of backtracking space. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_07615 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Verification Method for Graph Isomorphism Criteria Hu, Chuanfu Hou, Aimin Graphics The criteria for determining graph isomorphism are crucial for solving graph isomorphism problems. The necessary condition is that two isomorphic graphs possess invariants, but their function can only be used to filtrate and subdivide candidate spaces. The sufficient conditions are used to rebuild the isomorphic reconstruction of special graphs, but their drawback is that the isomorphic functions of subgraphs may not form part of the isomorphic functions of the parent graph. The use of sufficient or necessary conditions generally results in backtracking to ensure the correctness of the decision algorithm. The sufficient and necessary conditions can ensure that the determination of graph isomorphism does not require backtracking, but the correctness of its proof process is difficult to guarantee. This article proposes a verification method that can correctly determine whether the judgment conditions proposed by previous researchers are sufficient and necessary conditions. A subdivision method has also been proposed in this article, which can obtain more subdivisions for necessary conditions and effectively reduce the size of backtracking space. |
| title | Verification Method for Graph Isomorphism Criteria |
| topic | Graphics |
| url | https://arxiv.org/abs/2508.07615 |