# Graph properties along trajectories in $G(n,m)$

I consider a graph that changes randomly over (discrete) time denoted by $$(G_t)_{t=0}^{\infty}$$ where I call $$G_0=(V_0, E_0)$$, $$V_0$$ being the vertex and $$E_0$$ the edge set my initial condition where $$\mathrm{card}(V_0)=n$$.

Assuming that the dynamics preserve the vertex set and the number of edges, i.e., $$V_t=V_0$$ and $$\mathrm{card}(E_t)=\mathrm{card}(E_0)=m$$ for all $$t$$, and that $$G_0$$ is a $$\mathcal{G}(n,m)$$ graph can I say that $$G_t$$ at any time $$t$$ is also a $$\mathcal{G}(n,m)$$ graph and therefore apply results from theory of $$\mathcal{G}(n,m)$$ graphs? In particular, I would like to employ results on the largest connected component.

The dynamics itself consists of deleting and rewiring edges.

Right now I am torn between the fact that my dynamics give me a "trajectory" in $$\mathcal{G}(n,m)$$ and every $$G_t$$ could therefore be seen as a $$\mathcal{G}(n,m)$$ graph but $$G_t$$ is not just some random graph drawn from $$\mathcal{G}(n,m)$$ but the result of the dynamics started at $$G_0$$. I am not sure which one of the two is the right view on $$G_t$$.

• It depends on how exactly you "delete" and "rewire" edges. For example: if $G_t$ is obtained from $G_{t-1}$ by deleting a randomly chosen edge and adding another randomly chosen edge, then $G_t \sim \mathcal G(n,m)$. If $G_t$ is obtained from $G_{t-1}$ by deleting an edge from a higher degree vertex and joining two random low-degree vertices instead, this introduces a bias. – Misha Lavrov Nov 30 '18 at 18:19
• I color my vertices with two colors and delete edges that are incident to two vertices, say $i$ and $j$, with different colors. For the rewiring I pick uniformly one of the two vertices, say $i$, and draw uniformly from the vertices that are not adjacent to $i$. This will most likely introduce a bias, doesn't it? – Jfischer Dec 18 '18 at 6:52
• It seems like if you keep doing this for long enough, you will only be left with edges between vertices of the same color, which is very unlike a random graph, so yes. – Misha Lavrov Dec 18 '18 at 6:54