On matching extendability of lexicographic products
RAIRO - Operations Research, cilt.51, sa.3, ss.857-873, 2017 (Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 51 Sayı: 3
- Basım Tarihi: 2017
- Doi Numarası: 10.1051/ro/2016072
- Dergi Adı: RAIRO - Operations Research
- Derginin Tarandığı İndeksler: Scopus
- Sayfa Sayıları: ss.857-873
- Anahtar Kelimeler: Lexicographic product, Tutte's Theorem, ℓextendable graphs
- Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu
- Boğaziçi Üniversitesi Adresli: Evet
Özet
A graph G of even order is ℓextendable if it is of order at least 2â.," + 2, contains a matching of size â.,", and if every such matching is contained in a perfect matching of G. In this paper, we study the extendability of lexicographic products of graphs. We characterize graphs G and H such that their lexicographic product is not 1-extendable. We also provide several conditions on the graphs G and H under which their lexicographic product is 2-extendable.