Computing fixed point free automorphisms of graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918411634737152 |
|---|---|
| author | Abiad, Aida Coutinho, Gabriel Juliano, Emanuel Santos, Vinicius F. dos Zeijlemaker, Sjanne |
| author_facet | Abiad, Aida Coutinho, Gabriel Juliano, Emanuel Santos, Vinicius F. dos Zeijlemaker, Sjanne |
| contents | In 1981, Lubiw proved that the fixed point free automorphism problem (FPFAut) is NP-complete: given a graph G, determine whether there exists an automorphism that maps no vertex of G to itself. We revisit this problem and prove that FPFAut remains NP-complete when restricted to split, bipartite, k-subdivided, and H-free graphs, if H is not an induced subgraph of P_4. The class of P_4-free graphs receives the special name of cographs. We provide a polynomial time algorithm for three extensions of cographs: bounded modular-width graphs, tree-cographs and P_4-sparse graphs. Our approach uses the well known modular decomposition of graphs. As a consequence, we generalize a result of Abiad et. al. on the problem of computing 2-homogeneous equitable partitions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_26006 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Computing fixed point free automorphisms of graphs Abiad, Aida Coutinho, Gabriel Juliano, Emanuel Santos, Vinicius F. dos Zeijlemaker, Sjanne Discrete Mathematics Combinatorics In 1981, Lubiw proved that the fixed point free automorphism problem (FPFAut) is NP-complete: given a graph G, determine whether there exists an automorphism that maps no vertex of G to itself. We revisit this problem and prove that FPFAut remains NP-complete when restricted to split, bipartite, k-subdivided, and H-free graphs, if H is not an induced subgraph of P_4. The class of P_4-free graphs receives the special name of cographs. We provide a polynomial time algorithm for three extensions of cographs: bounded modular-width graphs, tree-cographs and P_4-sparse graphs. Our approach uses the well known modular decomposition of graphs. As a consequence, we generalize a result of Abiad et. al. on the problem of computing 2-homogeneous equitable partitions. |
| title | Computing fixed point free automorphisms of graphs |
| topic | Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2603.26006 |