## 1. Introduction

The paper Broom & Rychtář (2008) analytically investigated the probability for mutants to fixate in an otherwise uniform population on two types of heterogeneous graphs (lines and stars) by evolutionary dynamics. The main motivation for concentrating on those two types of graphs only was the potentially exponential size of the system of linear equations (see equation (1.1) below) yielding the fixation probability on general heterogeneous graphs. The size of the system was given by formula (4.1) from Broom & Rychtář (2008). It turns out that formula (4.1) is in fact only a lower bound for the size of the system and in this paper we correct this by deriving a formula for the exact size of the system (1.1). We also solve the system (1.1) for general heterogeneous graphs in the case of random drift.

Let *G*=(*V*,*E*) be an undirected graph, where *V* is the set of vertices and *E* is the set of edges. We assume that the graph is finite, connected and simple, i.e. no vertex is connected to itself and there are no parallel edges. The graph structure is represented by a matrix *W*=(*w*_{ij}), where
where *d*_{i} is the degree of the vertex *i*, i.e. the number of edges incident to the vertex *i*.

The evolutionary dynamics on graphs is described, e.g. in Lieberman *et al.* (2005) and is treated as a discrete time Markov chain. At the beginning, a vertex is chosen at random and replaced by a mutant with fitness *r*, all remaining vertices having fitness 1. At subsequent steps, a randomly chosen individual replicates with a probability proportional to its fitness and its offspring replaces an individual at a randomly chosen neighbouring vertex. The process stops when there are no mutants or no resident individuals in the graph. Each state of the dynamics is described by a set , a set of vertices inhabited by mutants.

Let *P*_{C} denote the probability of mutant fixation given that mutants currently inhabit a set *C*. The rules of the dynamics yield (Lieberman *et al.* 2005; Broom & Rychtář 2008)
1.1
with *P*_{∅}=0 and *P*_{V}=1. This system has a unique solution following Broom & Rychtář (2008).

For what classes of graphs can the system (1.1) be solved explicitly? Lieberman *et al.* (2005) solved it for regular graphs (where *d*_{i} takes a constant value independent of *i*, so that *w*_{ij}=*w*_{ji}). Broom & Rychtář (2008) solved it for stars and significantly reduced the size of the system for lines. Below, we shall solve the system for general graphs and *r* = 1, but first we consider the size of the system.

## 2. The number of mutant–resident formations

At every vertex of a graph *G*, there can be either a resident or a mutant; and thus there are up to 2^{|V |} potential mutant–resident formations or patterns. Let a mutant–resident formation be represented by a function *m*:*V* ↦{0,1} (0 for resident, 1 for mutant).

The (finite) automorphism group *Aut*(*G*) of the graph *G* acts on a set of formations *M*={*m*:*V* ↦{0,1}} by
2.1
for every vertex *v* whenever *f*∈*Aut*(*G*), *m*∈*M*. We say that two formations *m* and *m*′ are equivalent, if there is an automorphism *f* such that *m*′=*f*°*m* (and thus *m*=*f*^{−1}°*m*′). The number of unknowns in the system (1.1) is equal to the number of equivalence classes of mutant–resident formations |*M*/Aut(*G*)|. Burnside’s orbit counting theorem (Tucker 1994) yields
2.2
where |*M*^{f}| denotes the number of the elements of *M* fixed by *f*.

It is easy to see that if *f* is any permutation of vertices (this includes any automorphism of the graph), then *f*°*m*=*m* exactly for those *m* that are constant on the cycles of permutation *f*. Hence, if *C*(*f*) denotes the number of cycles of a permutation *f* (fixed points—as elements of *V* —of the permutation *f* count as one cycle), then every automorphism *f* fixes exactly 2^{C(f)} formations *m* because one can have only all 0’s or all 1’s on every cycle of *f*. Thus, the total count of equivalence classes of *m* and thus the number of mutant–resident formations, MRF(*G*), is given by
2.3

Consequently, as the number given by formula (2.3) is at least as large as the number given by formula (4.1) from Broom & Rychtář (2008), the main point of that paper is still valid as formula (4.1) was shown to emphasize the large size of the system (1.1) in a general heterogeneous graph.

## 3. Random drift, the case when *r* = 1

For the case of random drift, *r* = 1, the solution of equation (1.1) is given by
3.1
which can be checked by direct substitution. To derive the formula (3.1), assume that, for disjoint sets ,
3.2
By equation (3.2), the system (1.1) is equivalent to
which is satisfied if, for all *i*,*j*,

Consequently, whenever vertices *i* and *j* are connected,
3.3
As the graph is connected, the repeated application of equation (3.3) along a path between any two vertices *i*,*j* shows that equation (3.3) holds even when *i*,*j* are not connected by an edge. As, by equations (3.2) and (3.3),
3.4
we get
3.5
The formula (3.1) then follows from equations (3.5) and (3.2). The assumptions (3.2) and (3.3) can now be justified by the uniqueness of the solution of the system (1.1). Note that equation (3.2) cannot hold for general *r*. For example, if *r* is very large, which violates equation (3.2). Yet, as shown above, equation (3.2) holds when *r* = 1.

## 4. Discussion

The two results that we have presented apply for general graphs. Previous analytical papers, including Broom & Rychtář (2008), only consider very special graphs. The large size of the system of equations (1.1) makes it very difficult to find analytical results in the general case, of which equation (3.1) is a very special example. In fact, equation (2.3) is very useful in considering whether an analytical approach should be made, as the larger the value of MRF(*G*) the more difficult the system of equations is to deal with in general. Two of the simplest graphs that have received the most attention so far, the complete graph and the star, have values of MRF(*G*) of |*V* |+1 and 2|*V* |, respectively. Interestingly, the circle and the line, which have also been investigated, have much larger values of MRF(*G*), but many states cannot be accessed from the initial state of a single mutant (it was shown in Broom & Rychtář (2008) that these were the only graphs for which this was true).

## Footnotes

- Received February 8, 2010.
- Accepted March 5, 2010.

- © 2010 The Royal Society