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

Autor:	Valentin E. Brimkov, Reneta P. Barneva
Jazyk:	angličtina
Rok vydání:	2024
Předmět:	degree-equivalent graphs clique independent set vertex cover clique number independence number Mathematics QA1-939
Zdroj:	Mathematics, Vol 12, Iss 2, p 170 (2024)
Druh dokumentu:	article
ISSN:	2227-7390
DOI:	10.3390/math12020170
Popis:	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.
Databáze:	Directory of Open Access Journals
Externí odkaz:	https://doaj.org/article/4768dfc5c2384c8dacc14a93e4cdd595 Zobrazit plný text záznamu View record in DOAJ Plný text ve formátu PDF Plný text ve formátu HTML
Nepřihlášeným uživatelům se plný text nezobrazuje	K zobrazení výsledku je třeba se přihlásit.