|
-
October 24th, 2010, 12:35 PM
#6
Re: Number of ways of splitting a graph
 Originally Posted by StainlessSteel
I don't agree with the combinatorics, though, as:
If g is the number of vertices in the max-clique which can be members of the indep-set as well, we're ignoring the fact that there might be vertices in the independent set which might be members of the clique.
I don't think this case is possible since the clique is maximum:
Assume there is some vertex v in the IS which is connected to all vertices of the clique, it follows that degree(v) >= m and therefore it would have to be included in the clique on the first place.
Regards,
Zachm
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|