8

1

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.

flag
2 
 What happens if all the neighbours of $i$ are already adjacent to all the neighbours of $j$, so that you can't do the adding step without creating multiple edges? Do you stop? Do you not add edges before going on? – Olivier Nov 12 2011 at 14:36
1 
 The rules of this game don't make sense to me. At each step, you're deleting one edge and adding two, so the total number of edges increases by one. Forbidding multiple edges suggests the process terminates at some point (or else the graph is infinite). Also, why are the vertices for the new edges labeled with subscripts $t+1$? In particular, are the $i_{t+1}$ and $j_{t+1}$ intended to be the vertices chosen in the next step? (If so, then they are required to be adjacent.) – Barry Cipra Nov 12 2011 at 16:12
Olivier: If the neighbours are the same then you can not do anything. Nothing strange with that. When you have a random walk on a graph and your initial state is the limiting distribution then nothing changes. Barry: It is correct: at each time step I delete one edge and I add two. The graph is finite and so the process clearly terminates at some point. About the notation: sorry if you do not find it clear; please change it if you like. – Simone Severini Nov 12 2011 at 16:28
What the process does it to define a dynamical system. Analogously to the notion of "attractor" there will be some stable configurations. Starting the process with a graph there is a finite "state space". It is not clear to me which property of the graph determines the size of such state space. – Simone Severini Nov 12 2011 at 16:30

4 Answers

7

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.

link|flag
Thanks Barry for thinking about this. You got the spirit of the problem. I think I can prove that for any $n$-path with n larger than 3 we get the complete graph without a single edge -- I disregard trivial conditions. But I would be surprised if the terminal graphs, using your terminology, are either this one or the process does not start at all. There should be some more or less complicated (acyclic) endodiagrams with basis of attractions, etc. I will check what happens for 5 vertices as you suggested. Thanks again for your input. – Simone Severini Nov 12 2011 at 21:02
What happens if you have a 6-cycle ahibkj with a chord ij? According to @Barry's reduction this would turn into two copies of $K_3$, ahj and bik. Connectedness is therefore not preserved and this gives us a different terminal graph, also. – jpreen Nov 12 2011 at 21:46
1 
 Simone, let's label the 5 vertices A,B,C,D, and E. 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. – Barry Cipra Nov 12 2011 at 22:02
@jpreen, how is connectedness not preserved in the example you describe? If it's a cycle with a chord, then deleting the chord still leaves the cycle, which is connected, even before you add any more edges. – Barry Cipra Nov 12 2011 at 22:09
1 
 Suppose the edge ij is chosen where (say) j has degree 1. What is supposed to happen? Suppose the neighbor set of i in contained in the neighbor set of j? Then what? It is not clear that one is supposed to avoid such edges in the process. Gerhard "Ask Me About System Design" Paseman, 2011.11.13 – Gerhard Paseman Nov 13 2011 at 22:34
show 5 more comments
6

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.

link|flag
Sergey, I edited my answer to point to yours. – Barry Cipra Nov 14 2011 at 21:52
3

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$.

link|flag
Mark, it sounds like confluence means that you can "steer" two divergent graphs ($G_1$ and $G_2$) back together if you immediately take steps to do so, but it seems to me that's not what the OP is asking about. The OP wants to know which graphs $G$ wind up in the same terminal state no matter what steps are taken along the way. (Or maybe it's just me that wants to know that.) Am I missing something? – Barry Cipra Nov 13 2011 at 0:44
@Barry: These two facts are equivalent (Newman's diamond lemma) assuming the rewriting system is terminating (which is the case). – Mark Sapir Nov 13 2011 at 1:36
@Barry: if you do not want to read my survey, here is a Wiki article: en.wikipedia.org/wiki/Newman's_lemma – Mark Sapir Nov 13 2011 at 1:54
@ Mark: Thank you for the illuminating link with rewriting systems. I am now reading with interest your survey article. I am certainly learning things way beyond the topic of my question. @ Barry: Actually I did not think exactly about your idea, but this is also an interesting question too! – Simone Severini Nov 13 2011 at 19:53
Another survey on the Diamond Lemma is by George Bergman, in the '70's, I believe. He applies it to term rewriting in a variety of algebras. Gerhard "Ask Me About System Design" Paseman, 2011.11.13 – Gerhard Paseman Nov 13 2011 at 20:35
3

Here is an illustration of the rewiring process defined by Simone. Starting from this 10-node graph of 20 edges,
      Initial Graph
the process first deletes $(1,8)$ and adds $(1,10)$ and $(8,5)$:
      Initial Graph
The process then continues until the complete graph minus the edge $(1,8)$ is reached:
           Graph Rewiring Animation
Running the process on 10 random graphs, each of 10 nodes, results in terminating graphs with this many edges: $$(44, 41, 44, 40, 44, 44, 38, 44, 44, 37)$$ Note that $\binom{10}{2}=45$, so 6/10 ended at the complete graph minus one edge.

link|flag
@ Joseph: Thank you very much for this example! Did you write a Mathematica code for that? In case, can I please have it? @ All: I think that there are few interesting questions here. Of course maybe these turn out to be interesting only for me and completely worthless for you, but this is part of the game. I try to isolate two: 1) Given a graph G on n vertices find necessary and sufficient conditions on G such that one of the terminal graphs is Kn\e. 2) Given a graph G, define the number r(G), as the total number of terminal graphs. What can we say about r(G)? – Simone Severini Nov 13 2011 at 20:01
[Mathematica code sent privately to Simone.] – Joseph O'Rourke Nov 14 2011 at 12:02
2 
 If you take the complete graph and remove any number of edges incident with the same vertex, the result is a terminal graph. This gives 36-45 edges for 10 vertices. – Brendan McKay Nov 14 2011 at 13:09
1 
 @Brendan, I'm embarrassed not to have noticed this in my answer the other day. (I cited "complete minus one edge" and "complete minus two with a common vertex." Why I stopped there is inexplicable.) One small correction, though, to your observation: I think we're all assuming the starting (and hence terminal) graph is connected -- connectivity being unchanged by the process -- but if you remove all the edges incident on a vertex here, you've disconnected it from the rest of the graph, so maybe the proper range of terminal edges for 10 vertices should be 37-45. – Barry Cipra Nov 14 2011 at 14:26

Your Answer

Get an OpenID
or

Not the answer you're looking for? Browse other questions tagged or ask your own question.