Edge-stable equimatchable graphs
Yükleniyor...
Dosyalar
Tarih
2019
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Elsevier Science Bv
Erişim Hakkı
info:eu-repo/semantics/closedAccess
Özet
A 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.
Açıklama
10th International Colloquium on Graphs and Optimization (GO) -- JUL 10-14, 2016 -- Lucerne, SWITZERLAND
Deniz, Zakir/0000-0002-0701-0397; Ekim, Tinaz/0000-0002-1171-9294
WOS: 000468260200013
Deniz, Zakir/0000-0002-0701-0397; Ekim, Tinaz/0000-0002-1171-9294
WOS: 000468260200013
Anahtar Kelimeler
1-well-covered, Maximal matching, Edge-stability, Edge-criticality, Shedding vertex
Kaynak
Discrete Applied Mathematics
WoS Q Değeri
Q3
Scopus Q Değeri
Q2
Cilt
261
