Back to Search
Start Over
Bounds on the Clique and the Independence Number for Certain Classes of Graphs.
- Source :
-
Mathematics (2227-7390) . Jan2024, Vol. 12 Issue 2, p170. 14p. - Publication Year :
- 2024
-
Abstract
- In this paper, we study the class of graphs G m , n that have the same degree sequence as two disjoint cliques K m and K n , 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 G m , 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *INDEPENDENT sets
*REGULAR graphs
Subjects
Details
- Language :
- English
- ISSN :
- 22277390
- Volume :
- 12
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- Mathematics (2227-7390)
- Publication Type :
- Academic Journal
- Accession number :
- 175076593
- Full Text :
- https://doi.org/10.3390/math12020170