Edge decompositions of graphs
A graph, such as the cycle of 4 vertices, can be decomposed into two edge-disjoint copies of the path of length two.
The bipartite graph K_{2,3} can be decomposed into three edge-disjoint copies of the path of length two.
But when we attempt to decompose this graph with six edges into three copies of the path of length two, we have to be careful how we do it. If we start wrong, we may discover that we cannot finish the decomposition into three graphs all of which are paths. For example, in the drawing below, we might remove the blue path of length two and then the black path of length two. When we do that, we are left with the two reds edges which are not a path!
If the subgraph H has q edges then the number of edges in an H-decomposable graph G will be a multiple of q, say e=qa. The integer a indicates the height of the graph G as a collection of copies of H. The graph H, itself, has height 1; put together two copies of H to get a graph of height 2, and so on. The cycle C_4 in the first drawing, above, has height 2 as a P_2-decomposable graph while K_{2,3} has height 3.
The theory of edge decompositions of graphs is a large field of mathematical research. One may find it the subject of blog posts (here). There is at least one book (by ) published on the subject (which I found in my university library) and there is a study of infinite graphs and their simplicial decompositions (by Diestel). A nice introduction to the subject is in this brief survey paper (pdf) by Fan Chung and Ron Graham.
Randomly decomposable graphs
If G is decomposable into edge-disjoints copies of a graph H then we say G is H-decomposable. A partition of edges, each partition giving the subgraph H, is call an H-decomposition.In 1985, the Chilean mathematician Sergio Ruiz dealt with questions about graphs decompositions which remain decompositions even when the target subgraph H is "randomly" (or "thoughtlessly") removed. Given a fixed graph H, which graphs G are not just decomposable into copies of H but are decomposable in such a way that the decomposition cannot be "messed up".
For example, the cycle C_4 in the top picture is randomly decomposable into copies of H=P_2 while the bipartite graph K_{2,3} in the second and third pictures, is decomposable into copies of P_2, but is not "randomly" decomposable. The third picture shows a decomposition which fails.
The formal definition of randomly decomposable is the following. A graph G which is decomposable into copies of H is said to be randomly decomposable if the removal of the edges from any disjoint collection of copies of H leaves a graph which is still H-decomposable. We say that G is an RD with respect to H.
For example, if H=P_2 is the path of length 2 then the graph G=K_{2,3} fails the "randomly" decomposable requirement since if we remove -- in the third picture -- the black path 3-2-4 and the blue path 3-1-5, we get a graph which does not even involve a copy of H. So also C_4 is RD with respect to P_2, the graph K_{2,3} is not.
We can create a recursive definition equivalent to the one given above. (The first definition, above, is due to Ruiz.) The recursive definition defines the graph H to be "randomly" decomposable (of course) and then defines a graph G to be randomly decomposable if the removal of any copy of H leaves a randomly decomposable graph. This recursive definition suggests that we construct randomly decomposable graphs beginning with graphs of low height and adding copies of H, checking the "randomly" condition as we go.
Let us construct graphs which are randomly decomposable with respect to H=P_2, the path with just two edges. Pick a copy of H and label the vertices 1, 2 and 3 and assume the edges are {1,2} and {2,3} (so that H is the path 1-2-3.) Now take a second copy of H and assume the vertices are labelled a1, a2, a3 with a1 adjacent to a2 which is adjacent to a3. We may construct various P_2-decomposable graphs of height 2 by identifying certain vertices from the two copies.
First, if the vertices 1, 2, 3, a1, a2, a3 are all distinct, then the graph G is just two disconnected copies of H and so is clearly randomly decomposable.
If we identify the vertex 2 with the vertex a2 then we get the "star" with center 2 and end vertices 1,3, a1, a3. This graph, often written K_{1,4}, is randomly decomposable.
If we identify the vertex 1 with a1 and the vertex 3 with a3, we instead get the 4-cycle drawn in the first figure. This graph is randomly decomposable.
One can consider other ways to put together two copies of H=P_2, but all of those choices lead to graphs which although decompose into copies of P_2, do not decompose randomly! For example, if we just identify the vertices 1 and a1, we get a path 3-2-1-a2-a3 of length 4. This graph is not randomly decomposable since we could remove the path 2-1-a2 and be left with a graph which is not isomorphic to H.
Randomly decomposable graphs where H is a path
When I first heard Sergio Ruiz speak on this topic, I thought it should be fairly easy to find all randomly decomposable graphs in which the subgraph H is a path. But that turned out to be more complicated than I believed. For example, suppose H is a path of length 7. Then the graphs in the figure below are all RD with respect to H. And this is just height 2!!
I offer a brief exercise to test these RD ideas, prior to my next post:
Find all graphs which are RD with respect to the path of length 3 and have height two. (Feel free to stop at height two, using just two copies of P_3.)
I will give the solution to that exercise next time.
