Bounds on the Clique and the Independence Number for Certain Classes of Graphs
Bounds on the Clique and the Independence Number for Certain Classes of Graphs
In this paper, we study the class of graphs Gm,n that have the same degree sequence as two disjoint cliques Km and Kn, as well as the class G¯m,n of the complements of such graphs. The problems of finding a maximum clique and a maximum independent set are NP-hard on …