| 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.
nina.chiarelli@famnit.upr.si
2 Bogazici University, Dept. of Industrial Engineering, 34342, Bebek, Istanbul, Turkey.
cemil.dibek@boun.edu.tr; tinaz.ekim@boun.edu.tr
3 Gebze Technical University, Computer Engineering Dept., 41400 Gebze, Kocaeli, Turkey .
didem.gozupek@gtu.edu.tr
4 Andrej Marušič Institute, University of Primorska, Koper, Slovenia, and Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia.
stefko.miklavic@upr.si
Received: 6 March 2016
Accepted: 27 October 2016
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
© 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.