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.
Key-words Local computations - graph relabelling - enumerations - paths - minor - normal form of graph rewritings
This work has been supported by the EC TMR Network GETGRATS (General theory of Graph of Graph Transformation) through the
University of Bordeaux.
Member of the Institut universitaire de France.