hello all ,
There are two problems. I need a help on in discrete mathematic. which are:
1) A hole in a graph is an induced cycle of size 5 or more. An antihole is the complement of a hole. In this problem you are to consider the complements of odd cycles of size 5 or more.
Are odd antiholes (of size 5 or more) circular-arc graphs? Prove your answer. If no, argue that a circular-arc model cannot exist; if yes, describe how to construct a circular-arc model. Your answer must apply to ALL odd antiholes (not just 5-antiholes, or any specific size).
a) Give a graph for which the algorithm does not find a maximum size independent set.
b) Give the set the algorithm finds and explain how this arises.
c) Give a maximum independent set of a larger size.
Algorithm for that use in the second question is : Greedy Maximum Independent Set.
Given a graph G = (V, E), find a maximum size independent set I.
1. Choose a vertex x that has minimum degree to include in I.
x is our Greedy Choice.
2. Remove x and any neighbors of x from G.
3. Repeat 1 and 2 in the remaining graph. (Our optimal solution must include a maximum size independent set in the remaining graph.)
if anyone are able to help me on that . please let me know . thank’s