Computing fixed point free automorphisms of graphs
Summary
No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.
Summarise with VIRAT Free to try with your Science Catalogs account.Abstract
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.
Fields of Study & Subjects
Advanced Graph Theory Research
Complexity and Algorithms in Graphs
Graph Theory and Algorithms
Publication details
- Journal / source
- arXiv (Cornell University)
- Publication date
- 27 March 2026
- Language
- EN
- Document type
- Preprint