I am interested in a discrete process defined as follows. We start with a given graph. At each time step we delete an edge $(i,j)$ and add two edges $e$ and $f$; the edge $e$ is incident with $i$ and a neighbour of $j$ (which is not already a neighbour of $i$), and the edge $f$ is incident with $j$ and a neighbour of $i$ (which is not already a neighbour of $j$). A stable configuration is a graph in which a step of the process gives an isomorphic graph. I would like to collect some information about the behaviour of the process and its stable configurations.
Simone, this is really just a long comment rather than an answer, but I hope it'll be helpful.
First of all, thank you for the clarifications. If I understand correctly now, the process at each step requires finding a path of length 3, $hijk$, with $h$ not connected to $j$ and $i$ not connected to $k$. The step itself consists of deleting the edge $ij$ and adding edges $e = ik$ and $f=hj$, and the process terminates when there is no path that meets the requirements.
It seems sensible to start by describing which graphs are "terminal."
Note the process doesn't change the connectivity of the graph, so we may as well assume that the initial graph $G$ is connected.
One type of (connected) graph that is terminal is one that has no paths of length 3 at all -- i.e., a "star," all of whose edges emerge from a single, central point.
At the other end of the terminal spectrum are the complete graph, the complete graph minus one edge (I believe you mentioned this graph in an early version of the problem), and the complete graph minus two edges with a common vertex.
One pertinent question is, are there any other types of terminal graphs?
(Added 11/14/11: In a comment on Joseph O'Rourke's animated graphics, Brendan McKay notes that the complete graph minus any number of edges incident on a common vertex is terminal. How I failed to see that is anybody's guess. So the amended pertinent question is, does this exhaust the list of terminal graphs?)
(Added later on 11/14/11: Sergey Norin has effectively answered the amended pertinent question. The set of terminal graphs is precisely the set of "trivially perfect" graphs. See Sergey's answer for an explanatory link.)
I think what you're really asking is whether there are any graphs for which the selection of steps in the process can result in two different terminal graphs. It might be worth seeing what happens for connected graphs of small size, say with 5 or 6 vertices. (Actually 4 is a reasonable size to start with, but it doesn't take long to see that everything non-terminal terminates in the complete graph minus one edge.)
I tried one example with 5 edges: Starting from a single closed loop of length 5 (i.e., the perimeter of a pentagon), I found the process always terminates in the complete graph minus one edge. Maybe someone can flesh this out to a complete analysis of the 5-vertex case. Whether this will help understand what happens in general is anybody's guess, but at least it'd get things started.
Added 11/16/11: I'm adding something here that I originally posted as a comment, and expounding on it a little, because it may have gotten lost in the shuffle.
If you start with a complete graph minus the 3 edges AD, AE, and BC, then you can terminate in one step by deleting AB and adding AD and BC, or in two steps by deleting CD and adding AD and BC (followed by the deletion of DE and addition of AE and CD). So there certainly are some graphs for which the terminal state depends on the selection of steps.
Thus is may be of interest to distinguish between graphs whose terminal state is "predestined" regardless of the steps they take, and those that have "free will" to choose, say between the Heaven of one terminal state and the Hell of some other. E.g., the closed loop of length 5 is predestined to end as the complete graph (on 5 vertices) minus one edge, whereas the complete graph minus edges AD, AE, and BC has free will.
|show 5 more comments|
As Barry Cipra points out in his answer, the rewiring process continues as long as the graph contains some path $hijk$, such that $hj$ and $ik$ are not the edges of the graph. Equivalently, the terminal graphs are exactly the graphs which contain no induced subgraphs isomorphic to the $3$-edge path $P_4$ or to the $4$-cycle $C_4$. Such graphs have been studied before under the name trivially perfect graphs, and the Wikipedia page contains a number of equivalent characterizations of graphs in this class.
Consider your "rewriting process" as a rewriting system (see, for example, this survey, Section 2.9)) objects are graphs, moves are described by you and Barry Cipra. The question is whether the system is confluent, that is for every graph $G$ and every two moves $G\to G_1$, $G\to G_2$ there exists $G_3$ and a sequence of moves $G_1\to \to .... G_3 $, $G_2\to \to ...\to G_3$. Since your rewriting system is terminating, this would imply uniquencess of the "normal form", the terminal objects in your system in every connected component of the rewriting system containing a given graph (i.e. independence of the terminal object from the sequence of moves). The confluence can be proved as follows. Consider two paths of length 3 in the graph: $1-2-3-4$ and $5-6-7-8$. There are two moves corresponding to these subgraphs. If the paths do not have a common edge or if they share the edge $2-3=6-7$ (or $2-3=7-6$), then the confluence is obvious. In every other case, the union of the two paths is a subgraph with at most $6$ vertices. Thus to prove confluence you only need to consider graphs with at most 6 vertices composed of two paths of length 3 (extra edges cannot destroy the confluence, so the number of edges is at most 5). There are very few such graphs, and each case can be easily considered (I have not done checking myself). As a result, you either will find a counterexample among $\le 6$-vertex, $\le 5$-edge, graphs which are unions of two paths of length 3 or you will prove confluence of your rewriting system. Note that for each of these $\le 6$-vertex graphs you only need to resolve two moves $G\to G_1, G\to G_2$.
Here is an illustration of the rewiring process defined by Simone.
Starting from this 10-node graph of 20 edges,