• Support PF! Buy your school textbooks, materials and every day products Here!

H-decomposition problem

  • Thread starter Robb
  • Start date
221
8
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.
 

tnich

Homework Helper
1,019
326
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:
221
8
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
1,019
326
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.
 
221
8
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
 

Want to reply to this thread?

"H-decomposition problem" You must log in or register to reply here.

Related Threads for: H-decomposition problem

Replies
12
Views
2K
Replies
5
Views
817
Replies
2
Views
982
Replies
4
Views
1K
Replies
1
Views
4K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
5
Views
2K
Top