0
$\begingroup$

As we know, a tree-decomposition of a graph must have following features:

  1. All vertices are covered
  2. All edges are covered
  3. The connectivity condition

I think using repeated nodes in tree-decomposition must be allowed by definition. Is it true?

Edit:

The answer is here.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ What do you mean of repeated node? $\endgroup$ – Hoseyn Heydari Dec 8 '15 at 7:07
  • $\begingroup$ @Hoseyn Heydari, Assume you have created some nodes in a tree-decomposition so that all edges and vertices covered. Repeated nodes are nodes that copied from existent nodes and added to the tree-decomposition with retaining of connectivity condition. $\endgroup$ – Omid Ebrahimi Dec 8 '15 at 7:55
  • $\begingroup$ As it stands, your question is quit imprecise. Consider adding a full definition of tree decomposition (including references where appropriate). $\endgroup$ – user642796 Dec 9 '15 at 11:10
  • $\begingroup$ @Arthur Fischer, tree-decomposition is a known structure. Do you think it's necessary to define it again? In this case we must also define "graphs" when we ask a question about them (for example)! Whether or not, I'll set the Wikipedia reference in my question :) $\endgroup$ – Omid Ebrahimi Dec 9 '15 at 11:45
  • $\begingroup$ Yes, as a matter of fact, you must also define "graphs" when you ask a question about them. Can a graph have multiple edges? Can it have loops? Are the edges directed? Can the vertex set be infinite? Can the vertex set be empty? $\endgroup$ – bof Dec 9 '15 at 12:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.