Minor searching, normal forms of graph relabelling: two applications based on enumerations by graph relabelling

摘要

This paper deals with graph relabelling introduced in [LMS95]. Our first result concerns the open problem of searching a graph as a minor in a graph with a distinguished vertex, by means of graph relabellings. We give and prove a graph rewriting system which answers to this problem. Secondly we define and study normal forms of graph relabellings. We prove that any graph rewriting system can be simulated by a system in k-normal form (with an integer k depending on the original system). Proofs for both results are linked by the enumeration systems they used.