On matching extendability of lexicographic products

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

doi:10.1051/ro/2016072

Chiarelli, Nina ¹ ; Dibek, Cemil ² ; Ekim, Tınaz ² ; Gözüpek, Didem ³ ; Miklavič, Štefko ⁴

¹ FAMNIT and Andrej Marušič Institute, University of Primorska, 6000 Koper, Slovenia.
² Bogazici University, Dept. of Industrial Engineering, 34342, Bebek, Istanbul, Turkey.
³ Gebze Technical University, Computer Engineering Dept., 41400 Gebze, Kocaeli, Turkey
⁴ 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.

Résumé

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 : 2016-03-06
Accepté le : 2016-10-27

MR Zbl

DOI : 10.1051/ro/2016072

Classification : 05C70, 05C76
Mots-clés : ℓ-extendable graphs, lexicographic product, Tutte’s Theorem

Affiliations des auteurs :

Chiarelli, Nina ¹ ; Dibek, Cemil ² ; Ekim, Tınaz ² ; Gözüpek, Didem ³ ; Miklavič, Štefko ⁴

@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://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  - http://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 http://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. http://www.numdam.org/articles/10.1051/ro/2016072/

Bibliographie
Cité par

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

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

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

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. | DOI | MR | Zbl

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

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

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

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

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

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

Cité par Sources :