| Issue |
RAIRO-Oper. Res.
Volume 51, Number 3, July-September 2017
|
|
|---|---|---|
| Page(s) | 857 - 873 | |
| DOI | https://doi.org/10.1051/ro/2016072 | |
| Published online | 28 September 2017 | |
On matching extendability of lexicographic products∗
1 FAMNIT and Andrej Marušič Institute, University of Primorska, 6000 Koper, Slovenia.
This email address is being protected from spambots. You need JavaScript enabled to view it.
2 Bogazici University, Dept. of Industrial Engineering, 34342, Bebek, Istanbul, Turkey.
This email address is being protected from spambots. You need JavaScript enabled to view it.
; This email address is being protected from spambots. You need JavaScript enabled to view it.
3 Gebze Technical University, Computer Engineering Dept., 41400 Gebze, Kocaeli, Turkey .
This email address is being protected from spambots. You need JavaScript enabled to view it.
4 Andrej Marušič Institute, University of Primorska, Koper, Slovenia, and Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia.
This email address is being protected from spambots. You need JavaScript enabled to view it.
Received: 6 March 2016
Accepted: 27 October 2016
Abstract
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.
Mathematics Subject Classification: 05C70 / 05C76
Key words: ℓ-extendable graphs / lexicographic product / Tutte’s Theorem
This work has been supported by TUBITAK-ARRS under grant number 213M620. It is also supported in part by the Slovenian Research Agency (research program P1-0285 and research projects N1-0032, N1-0038, J1-5433, J1-6720, J1-7051).
© EDP Sciences, ROADEF, SMAI 2017
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.