Some results on Graph operators
by
B. Zelinka
Liberec

Let \Phi be a graph operator, let \Phi^r for a positive integer r denote its r-th iteration. If \Phi^r(G) =~ G and \Phi^s (G) for s < r is not isomorphic to G, we say that G is periodic in \Phi with periodicity r. If r=1, then G is fixed in \Phi.

The 2-distance operator T₂ and the 3-path-step operator S'₃ are operators which to a graph G assign consecutively the graphs T₂(G) and S'₃(G). The graph T₂(G) (or S'₃(G)) has the same vertex set as G and two vertices are adjacent in it if and only if their distance in G is 2 (or there exists a path of length 3 connecting them in G respectively). It is proved that there exist graphs of arbitrarily large periodicities in T₂; this is a solution of a problem from [Prisner. E.: ``Graph dynamics'', Longman House, Burnt Mill, Harlow (1998)]. Further all trees and unicyclic graphs fixed in S'₃ are listed.

Date received: May 26, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cafd-25.