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.

$\endgroup$
5
  • $\begingroup$ What do you mean of repeated node? $\endgroup$
    – Hoseyn Heydari
    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$
    – Omid Ebrahimi
    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$
    – Omid Ebrahimi
    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

0

Reset to default

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.