j***n
发帖数: 301 | 1 【 以下文字转载自 Mathematics 讨论区 】
发信人: jamen (jamen), 信区: Mathematics
标 题: Vertex Cover in Cubic Graph
发信站: BBS 未名空间站 (Fri Feb 20 22:24:44 2009), 转信
Hi Everyone,
I need to proof Vertex Cover problem is NP complete even for cubic graphs. N
otice that a cubic graph is a graph such that every vertex has degree of *ex
actly three*. I found one paper but his definition for cubic graph is a litt
le loose in that the degree can be less than 3.
Can anybody give me a hint?
Thanks! |
|
