Randomly Decomposable Graphs, III (Some open questions)

Some open questions in RDGs

In this third post on randomly decomposable graphs, we explore some open questions accessible to undergraduate students.  Partial results on these questions, for selected graphs, have just begun to appear in the mathematical literature and there are many, many trails to be explored in this area of the mathematical wilderness!

Fix a graph H and explore the poset RD(H) of all graphs G which are randomly decomposable with respect to H.  Recall that the height of a graph G in this poset is the number of edge-disjoint copies of H required to make G.  If the height of G is the integer a  and if H has q edges then G has e=aq edges.  A graph G is abundant with respect to H if there are more than a copies of H in G; G is trivial with respect to H if there are exactly a copies of H in G.  Thus the poset RD(H) partitions into two sets, the set,  RD_0(H), of trivial randomly decomposable graphs, and the set RD_A(H) of abundant randomly decomposable graphs.  Since H itself is a trivial member of RD(H), we can ask for minimal members of RD_A(H), that is, graphs which are abundantly RDG but have no subgraphs which are.

With this brief review, some basic mathematical questions jump out at us.

1. Given a fixed graph H, classify completely the members of RD(H).
2. Given a fixed graph H, list the minimally abundant members of RD(H).
3. Classify graphs H for which there are no abundant RDGs, that is, for which RD(H)=RD_0(H).
4. Are there graphs H for which RD(H) is finite?  Indeed, is it possible that RD(H)={H} for some graphs?

The first two questions invite experimentation with small graphs.  Choose a graph H with just 3 or 4 edges and first attempt to find the smallest abundant members of RD(H).  A helpful result in this area is the following lemma: 

"If G is minimally abundant with respect to H then the height of G 

is bounded above by the number of edges of H."  

Thus if H has only three edges, one need use at most three copies of H in building these smallest abundant RDGs.

If it is relatively easy to describe the minimal elements in RD_A(H), maybe it is possible to describe all of RD(H).  This has been done for graphs with two edges, and for the graphs H=P_3 and H=K_3 with three edges.  It has also been done for a few small paths and should be done for graphs with three or four edges.  Although describing RD(H) is somewhat easy for a few graphs (like H=K_3) this gets surprisingly difficult for other graphs (like H=C_4.)

Some graphs cannot create abundant RDGs.  This is true for the complete graphs, H=K_n, in which there are too many edges to allow one to build up RDGs that have "extra" copies of H.  Are there other graphs with this property?  Surely there are ... so can we classify, in some way, those graphs for which every RDG is trivial?

If H is connected then the graph aH, consisting of a components, each isomorphic to H, is in RD(H) and so the poset RD_0(H) is infinite.  But if H is not connected, then maybe RD(H) could be finite? When is RD(H) finite?  

I can argue that if H is the graph with three edges on five vertices, below,  formed from the path of length two and a disconnected edge, then RD(H)={H}!  (That graph, H = P_2 + K_1, is drawn below, using output from the Sage software program.)

For the student just beginning to explore RDGs: take a notebook and pen (or pencil) and draw a small graph H with three or four edges.  You might wish to choose one of the graphs drawn below.

Then begin constructing members of RD(H).  See if you can develop the first few members of RD(H) that involve 2, 3 or 4 copies of H.  Can you detect a pattern?  Can you make a statement about trivial or abundant graphs?  Drop me a line at kenwsmith54 (at) gmail (dot) com!

[Mathematical prerequisites: This article requires a basic introduction to randomly decomposable graphs (as seen in the previous  few blog posts).]

Follow Ken W. Smith on Twitter @kenwsmith54