Vertex maps on graphs-trace theorems
- PDF / 285,007 Bytes
- 11 Pages / 595.276 x 793.701 pts Page_size
- 38 Downloads / 179 Views
RESEARCH
Open Access
Vertex maps on graphs-trace theorems Chris Bernhardt Correspondence: [email protected] Fairfield University, Fairfield, CT 06824, USA
Abstract The paper proves two theorems concerning the traces of Oriented Markov Matrices of vertex maps on graphs. These are then used to give a Sharkoksky-type result for maps that are homotopic to the identity and that flip at least one edge. 2000 Mathematics Subject Classification 37E15, 37E25 Keywords: Graphs, Vertex maps, Periodic orbits, Sharkovsky’s theorem, Trace
1. Introduction A vertex map on a graph is a continuous map that permutes the vertices. Given a vertex map, the periods of the periodic orbits can be computed; giving a subset of the positive integers. One of the basic questions of combinatorial dynamics for vertex maps is to determine which subsets of the positive integers can be obtained in this way. Sharkovsky’s theorem [1] is a well-known result that answers the question when the underlying graph is topologically an interval and the vertices all belong to the same periodic orbit. In [2,3] a Sharkovsky-type theorem was proved for trees. In the vertex map papers, a standard method is to construct a matrix, called the Oriented Markov Matrix. The entries along main diagonal of the matrix give information about periodic orbits. In particular, the diagonal entries of the matrix raised to the nth power give information about the periodic orbits with period n. Thus the trace of powers of the matrix becomes important. In this paper, two results concerning the trace of powers of the Oriented Markov Matrix are proved. The first shows that the trace is a homotopical invariant. The second shows how the trace can be calculated from the number of edges in the graph and the number of vertices that are not fixed by the vertex map. These results follow from Hopf’s proof of the Lefschetz Fixed Point Theorem. However, since graphs are homologically very simple, it is possible to give elementary proofs, which we do. The trace theorems are then used to prove the following theorem. Theorem 1. Let G be a graph with v vertices. Let f be a vertex map on G that is homotopic to the identity and such that the vertices form one periodic orbit. Suppose f flips an edge. (1) If v is not a divisor of 2k then f has a periodic point with period 2k. (2) If v = 2pq, where q > 1 is odd and p ≥ 0, then f has a periodic point with period 2pr for any r ≥ q.
© 2011 Bernhardt; licensee Springer. This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Bernhardt Fixed Point Theory and Applications 2011, 2011:8 http://www.fixedpointtheoryandapplications.com/content/2011/1/8
Page 2 of 11
(Throughout the paper we will say that the period of a periodic point is the number of distinct points in its orbit. This is often referred to as the minimal or least period.)
Data Loading...
