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?


The answer is here.

  • $\begingroup$ What do you mean of repeated node? $\endgroup$ Dec 8, 2015 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$ Dec 8, 2015 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, 2015 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$ Dec 9, 2015 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, 2015 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.