Bounds on the Clique and the Independence Number for Certain Classes of Graphs

Valentin E. Brimkov and Reneta P. Barneva ()
Additional contact information
Valentin E. Brimkov: Mathematics Department, SUNY Buffalo State, Buffalo, NY 14222, USA
Reneta P. Barneva: School of Business, State University of New York at Fredonia, Fredonia, NY 14063, USA

Mathematics, 2024, vol. 12, issue 2, 1-14

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.

Keywords: degree-equivalent graphs; clique; independent set; vertex cover; clique number; independence number; vertex cover number; upper bound; lower bound (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/2/170/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/2/170/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:2:p:170-:d:1313630

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().