# H-decomposition problem

#### 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.
Homework 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.

Related Calculus and Beyond Homework Help News on Phys.org

#### tnich

Homework Helper
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.

Last edited:

#### 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

Homework Helper
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