1. Bounds on the Clique and the Independence Number for Certain Classes of Graphs
- Author
-
Valentin E. Brimkov and Reneta P. Barneva
- Subjects
degree-equivalent graphs ,clique ,independent set ,vertex cover ,clique number ,independence number ,Mathematics ,QA1-939 - Abstract
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 Gm,n. Therefore, looking for upper and lower bounds for the clique and independence numbers of such graphs is a challenging task. In this article, we obtain such bounds, as well as other related results. In particular, we consider the class of regular graphs, which are degree-equivalent to arbitrarily many identical cliques, as well as such graphs of bounded degree.
- Published
- 2024
- Full Text
- View/download PDF