Bipartite graphs with close domination and k-domination numbers

Basit Öğe Kaydı
dc.contributor.authorEkinci, Gulnaz Boruzanli
dc.contributor.authorBujtas, Csilla
dc.date.accessioned2020-12-01T11:58:30Z
dc.date.available2020-12-01T11:58:30Z
dc.date.issued2020
dc.departmentEge Üniversitesien_US
dc.description.abstractLet k be a positive integer and let G be a graph with vertex set V(G). A subset D subset of V(G) is a k-dominating set if every vertex outside D is adjacent to at least k vertices in D. the k-domination number gamma(k)(G) is the minimum cardinality of a k-dominating set in G. For any graph G, we know that gamma(k)(G) >= gamma(G) + k - 2 where Delta(G) >= k >= 2 and this bound is sharp for every k >= 2. in this paper, we characterize bipartite graphs satisfying the equality for k >= 3 and present a necessary and sufficient condition for a bipartite graph to satisfy the equality hereditarily when k = 3. We also prove that the problem of deciding whether a graph satisfies the given equality is NP-hard in general.en_US
dc.description.sponsorshipTUBITAK under the grant BIDEB 2221Turkiye Bilimsel ve Teknolojik Arastirma Kurumu (TUBITAK) [1059B211800686]; Slovenian Research AgencySlovenian Research Agency - Slovenia [N1-0108]en_US
dc.description.sponsorshipThis research was started when Csilla Bujtas visited the Ege University in Izmir, Turkey; the authors thank the financial support of TUBITAK under the grant BIDEB 2221 (1059B211800686). Csilla Bujtas also acknowledges the financial support from the Slovenian Research Agency under the project N1-0108.en_US
dc.identifier.doi10.1515/math-2020-0047
dc.identifier.endpage885en_US
dc.identifier.issn2391-5455
dc.identifier.issn2391-5455en_US
dc.identifier.scopus2-s2.0-85094137195en_US
dc.identifier.scopusqualityQ3en_US
dc.identifier.startpage873en_US
dc.identifier.urihttps://doi.org/10.1515/math-2020-0047
dc.identifier.urihttps://hdl.handle.net/11454/62034
dc.identifier.volume18en_US
dc.identifier.wosWOS:000564262900001en_US
dc.identifier.wosqualityQ3en_US
dc.indekslendigikaynakWeb of Scienceen_US
dc.indekslendigikaynakScopusen_US
dc.language.isoenen_US
dc.publisherDe Gruyter Poland Sp Z O Oen_US
dc.relation.ispartofOpen Mathematicsen_US
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/openAccessen_US
dc.subjectdomination numberen_US
dc.subjectk-domination numberen_US
dc.subjecthereditary propertyen_US
dc.subjectvertex-edge coveren_US
dc.subjectTC-numberen_US
dc.subjectcomputational complexityen_US
dc.titleBipartite graphs with close domination and k-domination numbersen_US
dc.typeArticleen_US

Dosyalar

Koleksiyon

WoS İndeksli Yayınlar Koleksiyonu
Scopus İndeksli Yayınlar Koleksiyonu