 Applied Mathematics, 2010, 1, 251-259 doi:10.4236/am.2010.14031 Published Online October 2010 (http://www.SciRP.org/journal/am) Copyright © 2010 SciRes. AM Some Models of Reproducing Graphs: II Age Capped Vertices Richard Southwell, Chris Cannings School of Mathematics and Statistics, University of Sheffield, Sheffield, United Kingdom E-mail: bugzsouthwell@yahoo.com Received June 26 , 20 10; revised August 10, 2010; accepted August 12, 2010 Abstract In the prequel to this paper we introduced eight reproducing graph models. The simple idea behind these models is that graphs grow because the vertices within reproduce. In this paper we make our models more realistic by adding the idea that vertices have a finite life span. The resulting models capture aspects of sys-tems like social networks and biological networks where reproducing entities die after some amount of time. In the 1940’s Leslie introduced a population model where the reproduction and survival rates of individuals depends upon their ages. Our models may be viewed as extensions of Leslie’s model-adding the idea of net-work joining the reproducing individuals. By exploiting connections with Leslie’s model we are to describe how many aspects of graphs evolve under our systems. Many features such as degree distributions, number of edges and distance structure are described by the golden ratio or its higher order generalisations. Keywords: Reproduction, Graph, Population, Leslie, Golden Ratio 1. Introduction Networks are everywhere, wherever a system can be t h o u g h t of as a collection of discrete elements, link ed up in some way, networks occur. With the acceleration of infor- mation technology more and more attention is being paid to the structure of these netwo rks, and this has led to the proposal of many models [1-3]. In many situations networks grow-expanding in size as material is produced from the inside, not added from outside. To study network growth we introduced a class of pure r eproduction models [4,5 ], where networks grow because the vertices within reproduce. These models can be applied to many situations where entities are intro- duced which derive their connections from pre existing elements. Most obviously they could be used to model social networks, collaboration networks, networks within growing organisms, the internet and protein-protein int erac tion networks. One of our systems (model 3) has also been introduced independently , proposed as a model for the growth of online social networks. In our pure reproduction models networks grow endlessly in a deterministic fashion. This allows a rigo- rous analysis, but costs a degree of realism. Nature in- cludes birth and death and entities may be destroyed for reasons of conflict, crowding or old age. In this paper we consider age; and extend our models by including vertex mortality. 2. The Models In  we defined a set {: {0,1,,7}}mFm of eight different functions mF which map graphs to graphs. ()mFG is the graph obtained by simultaneously giving each of G’s vertices an offspring vertex and then adding edges according to some rule. The connections given to offspring depend upon the binary representation  of m (i.e. =4 2m) as follows: =1 offspring are connected to their parent’s neighbours, =1 offspring are connected to their parents, =1 offspring are connected to their parent’s neighbour’s of fsp ri n g. In our age capped reproduction models we think of the vertices as having ages. Graphs grow under these models exactly as before, except that vertices grow and then die when their age exceeds some pre-specified integer Q. Our new update operator ,mQT is defined so that ,()mQTG is the graph obtained by taking the graph G and perfor- ming the following process; R. SOUTHWELL ET AL. Copyright © 2010 SciRes. AM 252 1) Increase the age of each vertex by one. 2) Give every vertex an age zero offspring, born with connectivity dependant upon m, as above (i.e. the new graph is ()mFG). 3) Remove every vertex with age greater than the age cap Q. We are interested in the sequence }{ tG of graphs which evolve from an initial structure 000=( ,)GVE in such a way that 1,=()tmQtGTG,0t . We always suppose that initial vertices have age Q. 3. The Number of Vertices The number of vertices ||tG in tG is deeply connected with the golden ratio and its generalisations. The number tin of age i vertices in tG can be conveniently descri- bed in terms of Leslie matrices. In Leslie’s population model [7,8] individuals of age i have a survival rate is and fertility rate if. The expected number of individuals of a given age, at a given time, is kept track of via repeated multiplication of the state vector with the ‘Leslie matrix’ 0120100 000 0.00 0QQfff fsss In our case 1=.ttnLn where 01=,,,Tttt tQnnn n and L is the Leslie matrix with ==1iisf , i. L is a primitive matrix with characteristic polyno- mial 1=0=QiQixx and principle eigenvalue Q (also known as the 1Q step Fibbonacci constant). The golden ratio is 1/2115=2, 2=1.8393,3=1.9276,4=1.9655 9 and2Q as Q. When t is large 1=ttQnn where  12=1, ,,,TQtQQ Qnc   is the stable age distribution and c is a constant which depends upon the initial state of the system. Let ,0 ,1,= (,,...,)Tiii iQd  where ji, is the Krone- cker delta. The n step Fibonacci numbers []nif are natural generalisations of the famous Fibonacci numbers  which can be generated by repeatedly multiplying 0d by L. When 0G is age zero (i.e. all its vertices have zero age) 00=| |.ttiinGLd, where 01.=tQtiiLd f. In such a case tG will have 02||.QtGf vertices. 4. Binary Strings As we update our graphs, their vertex sets will grow, and a good way to keep track of these vertex sets is to use binary strings. Suppose v is a vertex of 0G. When we update G we write (,0)v and (,1)v to denote v‘s offspring, and v itself (respectively), in the graph 1G. This means, for example, that (( ,0),0)v is the grand child of ((,1),1)v in 2G. We use short hand by omit- ting the parenthesis, so for example we write ,0),0)((v as 00v. An example of the evolution of model 2 is shown in Figure 1. When our age cap =Q an initial graph 000=( ,)GVE will evolve in exactly the same way as in pure repro- duction i.e. 0=()ttmGFG; this will have vertex set 0{0,1}tV and edge set as specified in . When Q is finite the situation is more complex, but our binary string notation allows us to keep track of the ages of vertices in a convenient way. Let ab denote the concatenation of binary strings a and b and let ta denote th e string obtained by conca- tenating a with itself t times. Suppose (01)nva is a vertex of tG for some 1{0,1}tna. Now (0)va is a new born offspring in tnG and every subsequent 1 in (01)nva ’s name corresponds to an update within which Figure 1. A depiction of the evolution of model 2 when =2Q, starting with an isolated vertex named p. R. SOUTHWELL ET AL. Copyright © 2010 SciRes. AM 253this vertex survives as a parent and gets older by one. It follows that (01)nva will be an age n vertex in tG. Theorem 1 If every vertex of the initial graph ),(= 000 EVG is age zero then tG will be the subgraph of 0()tiFG in- duced upon the vertex set tQWV 0, where ttQW{0,1} denotes the set of all t length binary strings which do not contain a run of 1Q consecutive 1’s. Proof Suppose tG is the subgraph of 0()tiFG induced upon 0tQVW, as is clearly the case when =0t. An age n vertex va in tG, with 0vV, will produce an offspring (0)va in 1tG. va will also survive to become (1)va iff 0=()... .tttiiiieSFend (4) Since the graphs we are concerned with are undirected we have tijtji ee ,,=, ji,. The average asymptotic rates of increase of the minimal and maximal degrees for the different models are given in Table 1. We use the term average because, under some models, these extremal degrees increase at varying rates dependant upon the time modulo 1Q. These rates where found by determining which binary string describes a vertex with maximal (or minimal) de- gree and using Equations (1) and (2). For example, su- ppose the initial graph 0G is age zero, and holds a vertex v with maximal degree, ()deg v, also suppose =.(1)tnQ c, for Qc. When =1m the vertex va , with =101nQca, will have maximal degree in tG. This vertex will have age sampling vector .ncQLSL 0(().)deg vd. The degree of the vertex with this form will increase by 1QQ every subsequent 1Q time steps, and so it follows that the average asymptotic rates of increase of the maximal degree when =1m is /( 1)1QQQ. Table 1. A table showing the average asymptotic growth rates of the minimal and maximal degrees under the different models m. The notation LIN(x) indicates that the extremal degrees increase linearly (as opposed to exponentially) with time with gradient x. m growth rate of the minimal degree growth rate of the maximal degr e e 0 0 0 1 0 /( 1)1()QQQ 2 0 1 3 1 /( 1)1()QQQ 4 1 1 5 Q Q 6 LIN( Q) LIN(1Q) 7 Q Q R. SOUTHWELL ET AL. Copyright © 2010 SciRes. AM 254 6. Connectivity, Degrees and Distances in Specific Models In this section we will focus on reproduction mechanisms with {1,2,3,5,6,7}m, one after another, and discuss the development of: connected components, number of edges, degree distributions, average path length and diameter. We do not discuss the dynamics when =0m or =4m because they are relatively uninteresting. Before we discuss the specifics it is worth pointing out an effect that occurs under many models. We say that a graph is age mixed when each of it edges connect a pair of vertices with different ages. If =0 and Qt> then tG will be age mixed. The reason is that when 0= offspring are not born connected to one another. So when Qt> all of the initial vertices will be dead, and tG will never again produce linked vertices with the same age. Saying that tG is age mixed has many implications, for example it means that tG has chromatic number Q because its vertices may be coloured according to their ages. 6.1. Aspects of Model 1 Suppose =1m and we begin with a connected graph. tG will typically consist of a growing connected component and lots of isolated vertices. In the special case when >=1tQ , updates do not cause the connected part of tG's structure to change. The reason is that tG is age mixed and every new born vertex either has a dead parent, which it replaces, or no surviving neighbours. Suppose 000=( ,)GVE is an age zero graph with 0uV. Any vertex ua of tG will be isolated iff a holds a run of 1Q consecutive zeros. To see this note that theorem 1, together with results from , imply that vb will be a neighbour of ua iff 0{,}uv E, tQbW and =0 =1iiab, i. Now if a holds a run of 1Q consecutive zeros then this means b holds a run of 1Q consecutive ones, which means tQbW, so no neighbour vb can actually exist. On the other hand if a does not hold a run of 1Q consecutive zeros, and 0},{Evu then tEvbua},{, where ii ab 1=, i. Let tiY denote the set of t length binary strings of the form iax where a is any it length string which does not hold a run of 1Q consecutive 0’s or a run of 1Q consecutive 1’s, and {0,1}: tixxa. By our argument above the number of non-isolated vertices in tG will be 0=1|| ||QtiiGY. For example consider a string 61100110 Y (when 2=Q), this string can be thought of as being responsible for generating the strings 711001101 Y and 721001100 Y at the next time step. Following similar reasoning one can see that, for generic Q, we have the difference equation; 1111221331|| ||11 11|| ||100 0=,|| ||01 00|| ||00 01 0ttttttttQQYYYYYYYY         which involves the QQ Leslie matrix. It follows that the number of non-isolated vertices in tG increases asymptotically at a rate of 1Q (whilst the total number of vertices grows at a rate of Q), meaning eventually almost every vertex of tG will be isolated. Although vertices do g et destr o yed during th e th e 1,QT they are always replaced by offspring which link to their old neighbours. The only way that a component of 0G could be disconnected under the update (in a non-trivial way) is if 0G has a cutset of edges that connect pairs of age Q vertices. This can only happen during the first Q updates. Regarding the edges, Equations (3) and (4) lose their dependance upon tin and ,>=0,tiitQ ei. Given these considerations we can reduce (3) and (4) to the following system of linear difference equations: ,{1,2,, }ij Q such that Q there will be less degree 1 vertices than degree 2 vertices when t is large. Global notions of distance (such as diameter) do not really make sense when 1=m because the structure is disconnected, with many isolated vertices. 6.2. Aspects of Model 2 Introducing an age cap into the 2=m model leads to fascinating self replicative behaviour. Whatever graph we begin with we end up with a set of special tree graphs that grow up and break into more tree graphs. Let tQS denote the graph obtained by starting with an age zero isolated vertex and evolving updating it with 2,QT, t times. This graph will have vertex set tQW and a pair of vertices ba, will be adjacent iff {1,2,,}kt  such that {1,2,, }it  we have ii baki =<, =ik iiab and 1==>ii baki . To understand the self replicative behaviour in tQS it helps to understand the self similarity of tS, the oldest and most central vertex of which is t1. Consider any neighbour nnt011 1 of t1. Since structures grow out of every vertex in the same way; the subgraph, tnX, induced upon the vertices 1{10:{0,1} }tn nxx  which grew out of nnt011 1 , over n time steps, will be age-isomorphic to the graph nS which grew out of the initial vertex, over n time steps (by age-isomorphic we mean there is a one to one mapping, from one vertex set to the other, which preserves the adjacency, non-adjacency and ages of the vertices). More generally =ttQSS when Qt , and 1QQS is the graph obtained by taking 1QS and removing the oldest vertex, 11Q. Since 1tQS is a tree, the removal of 11Q causes the graph to break into numerous components, namely 11 101,,,QQ QQXX X . Since 1QnX is age-iso- morphic to nS, it follows that 1QQS consists of 1Q different connected components, one age-isomorphic to nS for each Qn . Each of these connected components will evolve in the same manner-growing until the age of its central vertex exceeds Q, at which point it will fragment into yet more of these special trees. Any initial graph will evolve to become a set of these trees after 1Q time steps. The reason is that when 2=Qt all of the initial vertices will have died. This means the oldest surviving ancestor of any vertex in 2QG will be a vertex which was born when 0>t. If a pair of vertices lie within the same connected component in 2QG then they will have the same oldest surviving ancestor, and it follows that every connected component of 2QG is a tree structure which grew out of a vertex that was not initially present, and is hence age isomorphic to nS for Qn. Let tnC denote the number of connected components of tG which are age-isomorphic to nS for Qn. The vector 01=( ,, ,)ttt tTQCCC C satisfies the matrix equation ttCC .=1, where 00 0110 01=.01 0100 11 is equivalent to the transpose of the Leslie matrix L. It follows that when t is large tnC will increase at a rate of Q and the probability that a random connected component is age-isomorphic to iS will be (1)=0(1)=0 =01== .111ixiQQxiQy QxQQyx QpQ (8) The number of edges is described by the equations: 1101=0=.,Qttjjjend (9) 1110>0= ...tttiiiieSend (10) When Qt > we will have 0=,tiie, i. This implies that ,{0,1,,}: implies that tG will not hold any linked vertices with the same age. If 0G is connected then tG will usually be connected. When 0G has a cutset of edges connecting pairs of vertices with the same age then 3,0()QTG will be disconnected. This is the only way that structures can become disconnected, and it can only happen during the first Q updates. With respect to edge numbers, there are many similarities in the way that tG evolves when 1=m and 3=m. The only difference is that when 3=m offspring are connected to their parents, and this means that the equations which describe the evolution of tjie, gain a dependance upon the number of vertices. When Qt > we will have 0=,tiie, i, and we will hence have that: ,{1,2,,}ijQ such that ji <, 210,,11,1=0 ==Qitt ttini ininniee en (19) 1,1,1=ttiji jee (20) In the 1=m case the number of edges increase asym- ptotically at a rate of Q. The 3=m case is similar except that the number of edges is bolstered by the number of vertices tin, which increases at a lesser rate of Q. For large t the effect of these additional edges is hence negligible and the number of edges again increases at a rate of Q. Like the 1=m case computer simulations again suggest that when nt<1 we have 111.= .(),tQQtDn Dn (21) so the distribution again obeys a geometric law at the high end. When 1=Q we can describe the evolution of the degree distribution exactly for any initial graph 0G that is age mixed with no isolated vertices. Applying 3,1T to 0G is equivalent to changing the age of each vertex (from 0 to 1, and from 1 to 0) and then, for each age 1 vertex v, adding an age zero vertex that is only adjacent to v. Let )(dNtx denote the number of vertices of age x and degree d in tG. 0t we have 0,=(1)11tN (22) ,(1)=)((1)=(1) 0101=110tttitt nNiNNN   (23) ),(=)(1> 110dNdNd tt (24) 1).(=)(011dNdN tt (25) Solving these equations implies ,>0td {0,1}x R. SOUTHWELL ET AL. Copyright © 2010 SciRes. AM 257that when 21> xtd we have ,)/2()(1=)( 02mod1,1, xtdNdN xtdxtx (26) when 21= xtd we have (1),=)( 0100NndNtx (27) and when 21< xtd we have .=)(210dxttxndN  (28) When we introduce mortality our graphs seem to get longer. Diameter and average path length become greater. This is a result of the death of old vertices (which tend to be more central), this decreases the ease with which one can travel between the extremities. Let tL denote the sum of ),( vud for each ordered pair of vertices ),( vu in tG. The average length tl is equal to 2.| |ttLG. Let tjiU, denote the sum of the distances ),( vud between each ordered pair of vertices ),( vu from tG such that either u is of age i, v is of age j or u is of age j, v is of age i. When 1=Q the average length is given by 0,00,1 1,1201=.ttttttUUUlnn (29) When 3=m it seems as if both the average length and diameter of tG increase linearly with t whenever Q is finite. In the special case where 1=Q we can gain an exact description. Suppose that ),(= EVG is a connected age mixed graph; if u and v are age zero vertices of G then, after applying the 3,1T update, ),(=1)1,( vudvud , 1),(=1)0,( vudvud and (provided vu), (0,0)duv =(,)2duv. If u is age zero and v is age one in )(3,1 GT then after the update we have (1,0)duv=(,)duv and 1),(=0)0,( vudvud . If u and v are both of age one then after the update ),(=0)0,( vudvud . The diameter of tG will increase by two every two time steps and moreover the system obeys the equations 10,00,00,11,1001=2.1,tttttttUUUU nnn (30) 10,10,10,00 0=2 .tt tttUU Unn (31) .= 0,011,1 tt UU  (32) These equations imply that 1tL is equal to 21201110102. 2.42. 3.2 2.1,ttttttt tLLL nnnnn (33) which means that when t is large, the average length increases linearly with .15.1014.8=111tt ll (34) For 1>Q we have that )(3,1 GTt is a partial subgraph of )(3, GT tQ which is a partial subgraph of )(3, GT t. This implies that the curve which describes tl, for generic Q is bounded below by a constant (because of the =Q case, see ) and bounded above by a straight line. 6.4. Aspects of Model 5 In this case, when 0G is age zero, tG may be obtained by replacing each vertex v of 0G with a cluster vC of 2Qtf isolated vertices, and then connecting each vertex of uC to each vertex of vC whenever u and v where adjacent in 0G. It follows that 202()= ..Qtt QtnDnfD f (35) Equations (3) and (4) which describes the development of the edges may be cast as the matrix equation 100111122100 0=.00 0000 0ttttttttQQeeLLLLeeLeeLeeL          The matrix involved is clearly the Kronecker product of L with itself, it is hence primitive with principle eigenvalue 2Q. It follows that the asymptotic growth rate of the number of edges will be 2Q. Suppose our initial graph is connected, non-trivial and age zero. tG can be obtained by replacing each vertex by a cluster of 2Qtf vertices. Th is means every ordered pair ),( vu such that kvud =),(, in the initial graph gives rise to 1][ 21][ 2.QtQtff ordered pairs, spaced by distance k, in tG. In addition to this, every cluster adds  222. 1QQttff to the total distance, by the fact that every pair of distinct vertices within a given cluster will be spaced by distance 2. It follows that the total distance of tG will be [ 1][ 1][ 1]220220=. 2.1||.QQQQtt tttLffLffG (36) This means (irrespective of Q) that whe n t is large the average length approaches the constant ||2=00Gllt. The diameter of tG will be the maximum of the diameter R. SOUTHWELL ET AL. Copyright © 2010 SciRes. AM 258 of 0G and 2. 6.5. Aspects of Model 6 In this case tG will be a connected graph that can be obtained by taking the t dimensional hypercube graph and removing some vertices. The next graph in a sequence can be obtained by fusing together previous structures. For example when 1=> Qt , 1tG can be obtained by taking the disjoint union of tG and 1tG, choosing an isomorphism f from 1tG to the subgraph of tG induced upon its age zero vertices (such an isomorphism always exists) and adding an edge from each v vertex of 1tG to )(vf. The age one vertices of 1tG will be those which came from 1tG, vertices which came from tG will be age zero. The number of edges |||| tG, in tG, satisfies 10,0 =te || ||tG, tjitji ee 11,1,= and ,= 110, titine  0>,ji. This implies 11,=0 =|| ||=,QQ ttijijiGe (37) we can split the sums to get 1,1=10=1,0=1||=|| tjiQijQitiiQiteeG (38) making substitutions we find .||||||=||10=10=0=1itjiQjQiitQitnGG    (39) When t is large the minimal degree of tG becomes large-implying that the average degree also becomes large. This implies 111=0=0=0=0|| ||| |>QQ QQititi tijii ijGG n  (40) and so the asymptotic growth rate of the number of edges will be Q. Determination of the degree distribution when 6=m appears to be a difficult problem. Although some progress can be made when 1=Q the resulting formulae are long and complicated. With respect to distances it appears that the diameter and average length of tG increase linearly when t is large. We can show explicitly that this is the case when 1=Q. We say a graph is zero spanning if there is a shortest path between each pair of age zero vertices that only passes through age zero vertices. Updating any connected graph with 6,1T will always yield a zero spanning graph. Supposing that tG is a zero spanning graph, if u and v are age zero vertices of tG then after updating with 6,1T we will have ),(=0)0,(=1)1,( vudvudvud and 1),(=1)0,(vudvud. If u is age zero and v is age one in G then after the update we will have 1),(=0)1,(vudvud and ),(=0)0,( vudvud . If u and v are both age one vertices of G then after updating we will have ),(=0)0,( vudvud . This implies that the system obeys the equations: 10,00,00,11,1=ttttUUUU (41) 10,10,10,00 01=2tt ttttUU Unnn (42) 11,1 0,0=ttUU (43) These equations imply that as t the average length increases linearly with 12=5ttll The reasoning behind this is very similar to that when 1=Q and 3=m. The diameter of tG will increase by one every time step once the graph becomes zero spanning. 6.6. Aspects of Model 7 When our initial graph 0G is age zero tG may be obtained by replacing each vertex v of 0G with a complete graph vK on 1][ 2Qtf vertices, and then con- necting each vertex of uK to each vertex of vK when- ever u and v where adjacent in 0G. It follows that  220 21()= ..QQttt QtnfDn fDf (44) With respect to the edges this case is similar to the 5=m case, except that there is an extra dependence upon tin caused by the presence of edges linking offspring to their parents. 1000111112211100 000 0=00 000 00ttttttQttQQttLLLL SeeLBeeLBeeLBeeLnn            where nB is the 1)(1)( QQ matrix such that ,{0,1,,1}ijQ we have 0=,njiB, except that 1=0,nnB. In the 5=m case the number of edges increase asymptotically at a rate of 2Q. This 7=m case is similar except that the number of edges is bolstered by the number of vertices tin, which increases at a lesser rate of Q. For large t the effect of these additional edges is hence negligible and the number of edges again increases at a rate of 2Q. R. SOUTHWELL ET AL. Copyright © 2010 SciRes. AM 259Suppose our initial graph is connected, non-trivial and age zero. tG can be obtained by replacing each vertex by a complete graph on 2Qtf vertices. This means every ordered pair ),( vu such that kvud =),( , in the initial graph gives rise to  22.QQttff ordered pairs, spaced by distance k, in tG. In addition to this, every cluster adds  22.1QQttff to the total distance, by the fact that every pair of distinct vertices within a given cluster will be spaced by distance 1. It follows that the total distance of tG will be  220220=. 1||.QQQ Qtt tttLff LffG   (45) Interestingly this means that when t is large tl loses its dependance upon Q and approaches the constant ||1=00Gllt. The diameter of tG will be equal to the diameter of 0G. 7. Discussion We have discussed many properties of age capped models, however many open problems remain. These include describing degree distribution when {1,3,6}m and demonstrating the linearity of average length when {3,6}m (for generic Q). There are many directions in which our models may be expanded. As highlighted by theorem 1, our models may be regarded as an extension of pure reproduction models by adding restrictions upon the language of binary strings which the vertices can possess. Many other restrictions could be considered, e.g. forbidding the subword 01 1Q (which would correspond to saying vertices of age Q> become infertile). Our models can be viewed as an extension of Leslie's population model, introducing the idea of a network which connects the reproducing individuals. We will further develop this connection by considering the evo- lution of generic Leslie matrices (so that individuals of a given age can have differing numbers of offspring and chances of survival). Taking this approach and consi- dering connectivity as stochastic (so that , and  are probabilities, rather then binary integers) should yield models which directly simulate the development of ani- mal social networks and other phenomena. This paper demonstrates how our original reproducing graph models can be generalised in different directions whilst remaining analytically tractable. Perhaps the main reason these models are amenable to analysis is that the growth of one part of a graph is not influenced by the structure of another. This spatial independence allows one to understand the evolution of generic structures by studying the evolution of simple ones. There are many extensions of these models that it would be interesting to consider. In the future papers we will discuss the fascinating dynamics which can ensue when game theory is incorporated into these models. In this case we lose the spatial independence and dynamics of immense complexity become possible. It is also possible to extend many of the results here to cases where individuals produce several offspring-connected up in different ways. This kind of generalisation allows one model how the social networks of specific types of organisms grow in a more direct way. 8. Acknowledgements The authors gratefully acknowledge support from the EPSRC (Grant EP/D003105/1) and helpful input from Dr Jonathan Jordan, and others in the Amorph Research Project (www.amorph.group.shef.ac.uk). 9. References  P. Erdös and A. Rényi, “On Random Graphs. I,” Publica-tiones Mathematicae, Vol. 6, 1959, pp. 290-297.  G. U. Yule, “A Mathematical Theory of Evolution, Based on the Conclusions of Dr. J. C. Willis, F. R. S.,” Phi-losophical Transactions of the Royal Society of London, B, Vol. 213, 1925, pp. 21-87.  D. J. Watts and S. H. Strogatz, “Collective Dynamics of ‘Small-World’ Networks,” Nature, Vol. 393, No. 6684, 1998, pp. 440-442.  R. Southwell and C. Cannings, “Games on Graphs that Grow Deterministically,” Proceedings of International Conference on Game Theory for Networks GameNets ‘09, Istanbul, Turkey, 2009, pp. 347-356.  R. Southwell and C. Cannings, “Some Models of Repro-ducing Graphs: I Pure Reproduction,” Journal of Applied Mathematics, Vol. 1, No. 3, 2010, pp. 137-145.  A. Bonato, N. Hadi, P. Horn, P. Praalat and C. Wand, “Models of On-Line Social Networks,” To appear in In-ternet Mathematics, 2010.  P. H. Leslie, “The Use of Matrices in Certain Population Mathematics,” Biometrika, Vol. 30, 1945, pp. 183-212.  P. H. Leslie, “Some Further Notes on the Use of Matrices in Population Mathematics,” Biometrika, Vol. 35, No. 3-4, 1948, pp. 213-245.  T. D. Noe, “Primes in Fibonacci n-step and Lucas n-step Sequences,” Journal of Integer Sequences, Vol. 8, 2005, pp. 1-12.