A classification of 1-well-covered graphs
Yükleniyor...
Dosyalar
Tarih
2021
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Scientific Technical Research Council Turkey-Tubitak
Erişim Hakkı
info:eu-repo/semantics/closedAccess
Özet
A graph is well-covered if all its maximal independent sets have the same size. If a graph is well-covered and remains well-covered upon removal of any vertex, then it is called 1-well-covered graph. It is well-known that [n/2] + 1 <= alpha(G) mu(G) <= n for any graph G with n vertices where alpha(G) and mu(G) are the independence and matching numbers of G, respectively. A graph G satisfying alpha(G) + mu(G) = n is known as Konig-Egervary graph, and such graphs are characterized by Levit and Mandrescu [14] under the assumption that G is 1-well-covered. In this paper, we investigate connected 1-well-covered graphs with respect to alpha(G) + mu(G) = n - k for k >= 1 and vertical bar G vertical bar = n. We further present some combinatorial properties of such graphs. In particular, we provide a tight upper bound on the size of those graphs in terms of k, namely vertical bar G vertical bar <= 10k - 2, also we show that Delta(G) <= 2k + 1 and alpha(G) <= min{4k - 1,n - 2k}. This particularly enables us to obtain a characterization of such graphs for k = 1, which settles a problem of Levit and Mandrescu [14].
Açıklama
Anahtar Kelimeler
Independent Set; Matching; Well-Covered, Konig-Egervary Graphs; Well-Covered Graphs
Kaynak
Turkish Journal of Mathematics
WoS Q Değeri
Q3
Scopus Q Değeri
Q2
Cilt
45
Sayı
6
