no. 3
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

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},
     year = {2017},
     publisher = {EDP Sciences},
     volume = {51},
     number = {3},
     doi = {10.1051/ro/2016072},
     zbl = {1387.05193},
     mrnumber = {3880529},
     language = {en},
     url = {https://www.numdam.org/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  - https://www.numdam.org/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 https://www.numdam.org/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

B. Bai, Z. Wu, X. Yang and Q. Yu, Lexicographic product of extendable graphs. Bull. Malays. Math. Sci. Soc. 33 (2010) 197–204. | Zbl | MR

O. Chan, C. Chen and Q. Yu, On 2-extendable Abelian Cayley graphs. Discrete Math. 146 (1995) 19–32. | Zbl | MR | DOI

E. Győri and W. Imrich, On the strong product of a k-extendable and an ℓ-extendable graph. Graphs Combin. 17 (2001) 245–253. | Zbl | MR | DOI

E. Győri and M.D. Plummer, The Cartesian product of a k-extendable and l-extendable graph is (k+l+1)-extendable. Discrete Math. 101 (1992) 87–96. | Zbl | MR | DOI

W. Imrich and S. Klavžar, Product Graphs, structure and recognition. John Wiley & Sons, Inc., New York (2000). | Zbl | MR

C.H.C. Little, D.D. Grant and D.A. Holton, On defect-d matchings in graphs. Discrete Math. 13 (1975) 41–54. | Zbl | MR | DOI

J.P. Liu and Q.L. Yu, Matching extensions and products of graphs. Ann. Discrete Math. 55 (1993) 191–200. | Zbl | MR | DOI

M.D. Plummer. On n-extendable graphs. Discrete Math. 31 (1980) 201–210. | Zbl | MR | DOI

W.T. Tutte, The factorization of linear graphs. J. London Math. Soc. 22 (1947) 107–111. | Zbl | MR | DOI

Q.R. Yu and G. Liu, Graph Factors and Matching Extensions. Springer-Verlag, Berlin (2010). | Zbl | MR

Cité par Sources :