Edge-stable equimatchable graphs

Basit Öğe Kaydı
dc.contributor.authorDeniz, Zakir
dc.contributor.authorEkim, Tınaz
dc.date.accessioned2020-05-01T09:11:34Z
dc.date.available2020-05-01T09:11:34Z
dc.date.issued2019
dc.departmentDÜ, Fen-Edebiyat Fakültesi, Matematik Bölümüen_US
dc.description10th International Colloquium on Graphs and Optimization (GO) -- JUL 10-14, 2016 -- Lucerne, SWITZERLANDen_US
dc.descriptionDeniz, Zakir/0000-0002-0701-0397; Ekim, Tinaz/0000-0002-1171-9294en_US
dc.descriptionWOS: 000468260200013en_US
dc.description.abstractA graph G is equimatchable if every maximal matching of G has the same cardinality. We are interested in equimatchable graphs such that the removal of any edge from the graph preserves the equimatchability. We call an equimatchable graph G edge-stable if G \ e, that is the graph obtained by the removal of edge e from G, is also equimatchable for any e is an element of E(G). After noticing that edge-stable equimatchable graphs are either 2-connected factor-critical or bipartite, we characterize edge-stable equimatchable graphs. This characterization yields an O(min(n(3.376), n(1.5)m)) time recognition algorithm. Lastly, we introduce and shortly discuss the related notions of edge-critical, vertex-stable and vertex critical equimatchable graphs. In particular, we emphasize the links between our work and the well-studied notion of shedding vertices, and point out some open questions. (C) 2018 Elsevier B.V. All rights reserved.en_US
dc.description.sponsorship[213M620]en_US
dc.description.sponsorshipThe support of Turkish-Slovenian TUBITAK-ARSS Joint Research Project grant no: 213M620 is greatly acknowledged. The authors are also grateful to the anonymous referees for their helpful suggestions to improve the paper.en_US
dc.identifier.doi10.1016/j.dam.2018.09.033en_US
dc.identifier.endpage147en_US
dc.identifier.issn0166-218X
dc.identifier.issn1872-6771
dc.identifier.scopusqualityQ2en_US
dc.identifier.startpage136en_US
dc.identifier.urihttps://doi.org/10.1016/j.dam.2018.09.033
dc.identifier.urihttps://hdl.handle.net/20.500.12684/5668
dc.identifier.volume261en_US
dc.identifier.wosWOS:000468260200013en_US
dc.identifier.wosqualityQ3en_US
dc.indekslendigikaynakWeb of Scienceen_US
dc.indekslendigikaynakScopusen_US
dc.language.isoenen_US
dc.publisherElsevier Science Bven_US
dc.relation.ispartofDiscrete Applied Mathematicsen_US
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/closedAccessen_US
dc.subject1-well-covereden_US
dc.subjectMaximal matchingen_US
dc.subjectEdge-stabilityen_US
dc.subjectEdge-criticalityen_US
dc.subjectShedding vertexen_US
dc.titleEdge-stable equimatchable graphsen_US
dc.typeArticleen_US

Dosyalar

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

Koleksiyon

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