Geodesic
On matching extendability of lexicographic products
Chiarelli, Nina1 ; Dibek, Cemil2 ; Ekim, Tınaz2 ; Gözüpek, Didem3  ; Miklavič, Štefko4
1 FAMNIT and Andrej Marušič Institute, University of Primorska, 6000 Koper, Slovenia.
2 Bogazici University, Dept. of Industrial Engineering, 34342, Bebek, Istanbul, Turkey.
3 Gebze Technical University, Computer Engineering Dept., 41400 Gebze, Kocaeli, Turkey
4 Andrej Marušič Institute, University of Primorska, Koper, Slovenia, and Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia.
RAIRO - Operations Research - Recherche Opérationnelle, Tome 51 (2017) no. 3, pp. 857-873

Voir la notice de l'article provenant de la source Numdam

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.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2016072
Classification : 05C70, 05C76
Keywords: ℓ-extendable graphs, lexicographic product, Tutte’s Theorem

Chiarelli, Nina 1 ; Dibek, Cemil 2 ; Ekim, Tınaz 2 ; Gözüpek, Didem 3 ; Miklavič, Štefko 4

1 FAMNIT and Andrej Marušič Institute, University of Primorska, 6000 Koper, Slovenia.
2 Bogazici University, Dept. of Industrial Engineering, 34342, Bebek, Istanbul, Turkey.
3 Gebze Technical University, Computer Engineering Dept., 41400 Gebze, Kocaeli, Turkey
4 Andrej Marušič Institute, University of Primorska, Koper, Slovenia, and Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia. 
@article{RO_2017__51_3_857_0,
     author = {Chiarelli, Nina and Dibek, Cemil and Ekim, T{\i}naz and G\"oz\"upek, Didem and Miklavi\v{c}, \v{S}tefko},
     title = {On matching extendability of lexicographic products},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {857--873},
     publisher = {EDP-Sciences},
     volume = {51},
     number = {3},
     year = {2017},
     doi = {10.1051/ro/2016072},
     zbl = {1387.05193},
     mrnumber = {3880529},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2016072/}
}
TY  - JOUR
AU  - Chiarelli, Nina
AU  - Dibek, Cemil
AU  - Ekim, Tınaz
AU  - Gözüpek, Didem
AU  - Miklavič, Štefko
TI  - On matching extendability of lexicographic products
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2017
SP  - 857
EP  - 873
VL  - 51
IS  - 3
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ro/2016072/
DO  - 10.1051/ro/2016072
LA  - en
ID  - RO_2017__51_3_857_0
ER  - 
%0 Journal Article
%A Chiarelli, Nina
%A Dibek, Cemil
%A Ekim, Tınaz
%A Gözüpek, Didem
%A Miklavič, Štefko
%T On matching extendability of lexicographic products
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2017
%P 857-873
%V 51
%N 3
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ro/2016072/
%R 10.1051/ro/2016072
%G en
%F RO_2017__51_3_857_0
Chiarelli, Nina; Dibek, Cemil; Ekim, Tınaz; Gözüpek, Didem; Miklavič, Štefko. On matching extendability of lexicographic products. RAIRO - Operations Research - Recherche Opérationnelle, Tome 51 (2017) no. 3, pp. 857-873. doi: 10.1051/ro/2016072

Cité par Sources :