A classification of 1-well-covered graphs

Yükleniyor...
Küçük Resim

Tarih

2021

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

Künye