A classification of 1-well-covered graphs

Basit Öğe Kaydı
dc.authoridDeniz, Zakir/0000-0002-0701-0397
dc.authorwosidDeniz, Zakir/AAK-6689-2021
dc.contributor.authorDeniz, Zakir
dc.date.accessioned2023-07-26T11:49:55Z
dc.date.available2023-07-26T11:49:55Z
dc.date.issued2021
dc.departmentDÜ, Fen-Edebiyat Fakültesi, Matematik Bölümüen_US
dc.description.abstractA 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].en_US
dc.description.sponsorshipTUBITAK (The Scientific and Technological Research Council of Turkey) [121F018]en_US
dc.description.sponsorshipThis research has been supported by TUBITAK (The Scientific and Technological Research Council of Turkey) under the project number 121F018. The author would like to thank the anonymous referee for useful suggestions that improved the presentation of this work. The author also would like to thank Mehmet Akif Yetim for many helpful discussions.en_US
dc.identifier.doi10.3906/mat-2105-45
dc.identifier.endpage2829en_US
dc.identifier.issn1300-0098
dc.identifier.issn1303-6149
dc.identifier.issue6en_US
dc.identifier.scopus2-s2.0-85121798002en_US
dc.identifier.scopusqualityQ2en_US
dc.identifier.startpage2817en_US
dc.identifier.trdizinid528505en_US
dc.identifier.urihttps://doi.org/10.3906/mat-2105-45
dc.identifier.urihttps://search.trdizin.gov.tr/yayin/detay/528505
dc.identifier.urihttps://hdl.handle.net/20.500.12684/12168
dc.identifier.volume45en_US
dc.identifier.wosWOS:000722195400001en_US
dc.identifier.wosqualityQ3en_US
dc.indekslendigikaynakWeb of Scienceen_US
dc.indekslendigikaynakScopusen_US
dc.indekslendigikaynakTR-Dizinen_US
dc.institutionauthorDeniz, Zakir
dc.language.isoenen_US
dc.publisherScientific Technical Research Council Turkey-Tubitaken_US
dc.relation.ispartofTurkish Journal of Mathematicsen_US
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/closedAccessen_US
dc.snmz$2023V1Guncelleme$en_US
dc.subjectIndependent Set; Matching; Well-Covereden_US
dc.subjectKonig-Egervary Graphs; Well-Covered Graphsen_US
dc.titleA classification of 1-well-covered graphsen_US
dc.typeArticleen_US

Dosyalar

Orijinal paket
Listeleniyor 1 - 1 / 1
Küçük Resim
İsim:
12168.pdf
Boyut:
213.4 KB
Biçim:
Adobe Portable Document Format
Açıklama:
Tam Metin / Full Text
İndir

Koleksiyon

WoS İndeksli Yayınlar Koleksiyonu
Scopus İndeksli Yayınlar Koleksiyonu
TR-Dizin İndeksli Yayınlar Koleksiyonu