Showing cs.DMShow all
3 papers · 1 filter
cs.DM2026
Computing fixed point free automorphisms of graphs
Aida Abiad, Gabriel Coutinho, Emanuel Juliano +2
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…
cs.DM2025
Exploring subgraph complementation to bounded degree graphs
Ivo Koch, Nina Pardal, Vinicius F. dos Santos
Graph modification problems are computational tasks where the goal is to change an input graph using operations from a fixed set, in order to make the resulting graph satisfy a…
cs.DM2024
Complexity of Deciding the Equality of Matching Numbers
Guilherme C. M. Gomes, Bruno P. Masquio, Paulo E. D. Pinto +4
A matching is said to be disconnected if the saturated vertices induce a disconnected subgraph and induced if the saturated vertices induce a 1-regular graph. The disconnected and…