Starfish graphs are made of one central cycle and a bunch of tentacles. When drawn appropriately they can look like starfish. More formally, a starfish graph has k vertices of degree 4 and k vertices of degree 2, with the degree-4 vertices arranged in a cycle and the degree-2 vertices making up each tentacle. Setting k=5 yields the traditional 5-tentacled beast. Apparently, the H-cover problem is NP-Complete even for simple graphs like starfish.
No comments:
Post a Comment