What is the structure of an H-decomposable graph?

[Robb]

Homework Statement

Show that if a graph G of size m contains a subgraph H of size m' where m' divides m, then G need not be decomposable.

Relevant Equations

N/A

Can someone please explain H-decomposable graphs. I understand that if all the subgraphs $H_1, H_2, ..., H_k$ are isomorphic to the same graph H, then G is H-decomposable. What I don't understand is, what is H? I'm reading this as there is a subgraph H, that contains a family of subgraphs $H_1, H_2, ..., H_k$, which doesn't make sense to me. I thought the subgraphs $H_1, H_2, ..., H_k$ were the decomposition of G. Please advise.

 

[tnich]

Here is an abstract with a definition of H-decomposition: https://www.scirp.org/journal/PaperInformation.aspx?PaperID=24522. It looks different than what you have stated. In this definition, graph G is partitioned into subsets of the edges, such that each subset is isomorphic to H or contains a single edge. So every node either has only one edge, or is in one and only one subgraph isomorphic to H. The union of these subgraphs and the single edges is G. This leaves open the possibilities of isolated pairs of nodes connected by a single edge and nodes with a single edge connected to an H graph.

 

[Robb]

Here is an abstract with a definition of H-decomposition: https://www.scirp.org/journal/PaperInformation.aspx?PaperID=24522. It looks different than what you have stated. In this definition, graph G is partitioned into subsets of the edges, such that each subset is isomorphic to H or contains a single edge. So every node either has only one edge, or is in one and only one subgraph isomorphic to H. The union of these subgraphs and the single edges is G. This leaves open the possibilities of isolated pairs of nodes connected by a single edge and nodes with a single edge connected to an H graph.

Thanks, I don't suppose you would have an example of the graphs G and H, and possibly the partitions?

 

[tnich]

I don't, but you could construct them yourself. Draw a graph H. It can be any graph - large, small, highly connected or not. Draw a few copies of it. Pick a pair of the H graphs and draw an edge between a node in one and a node in the other. Repeat for another pair of H graphs. You can keep this up until the final graph is connected, or not. If you want you could also add a node connected to one H group with an edge, or a pair of nodes connected with an edge but not connected to anything else.

 

[Robb]

I don't, but you could construct them yourself. Draw a graph H. It can be any graph - large, small, highly connected or not. Draw a few copies of it. Pick a pair of the H graphs and draw an edge between a node in one and a node in the other. Repeat for another pair of H graphs. You can keep this up until the final graph is connected, or not. If you want you could also add a node connected to one H group with an edge, or a pair of nodes connected with an edge but not connected to anything else.

THanks