Computing fixed point free automorphisms of graphs

Read full text Summarise with VIRAT
Authors: Aida Abiad, Gabriel Coutinho, Emanuel Juliano, Vinícius F. dos Santos, Sjanne Zeijlemaker
Cited by: 0
References: 29

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