Author |
Topic: NEW PROBLEM: MORE SPANNING TREES (Read 2013 times) |
|
Pietro K.C.
Full Member
 
Gender: 
Posts: 213
|
 |
NEW PROBLEM: MORE SPANNING TREES
« on: Sep 24th, 2002, 1:28pm » |
 Quote  Modify
|
Let G = (V, E) be an undirected grap, and consider the problem of finding out whether G has a spanning tree where every vertex has degree less than or equal to k.
Show that P is NP-complete.
Note: the degree referred to is the degree a vertex has in the spanning tree, not in the whole graph, because then all degrees would be predetermined, and P would be no fun at all.  For example, consider a triangle ABC, where sides are edges and vertices are - well, vertices. Then all nodes have degree two. However, in the spanning tree {(A,B),(B,C)}, A and C have degree 1.
|
|
 IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print