Matching extendability in Cartesian products of cycles. (English) Zbl 1490.05221
Summary: In a bipartite graph \(G\), a set \(S\subseteq V(G)\) is deficient if \(|N(S)|<|S|\). A matching \(M\) with vertex set \(U\) is \(k\)-suitable if \(G-U\) has no deficient set of size less than \(k\). Define the extremal function \(f_k(G)\) to be the largest integer \(r\) such that every \(k\)-suitable matching in \(G\) with at most \(r\) edges extends to a perfect matching. Let \(G(2m)_d\) be the \(d\)-fold Cartesian product of the cycle \(C_{2m}\), where \(m\geq 2\). We extend results of J. Vandenbussche and D. B. West [SIAM J. Discrete Math. 23, No. 3, 1539–1547 (2009; Zbl 1207.05161)] by showing that for any integers \(k\) and \(d\) such that \(1\leq k\leq d\), \(f_k(G(2m)_d)=k(2d(-k)+k\binom{k-1}{2}\), except when \(m=2\) and \(d=1\).
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C76 | Graph operations (line graphs, products, etc.) |
| 05C38 | Paths and cycles |
Citations:
Zbl 1207.05161Software:
MathematicaReferences:
| [1] | R. E. L. Aldred, J. Fujisawa and A. Saito, Distance matching extension and local structure of graphs,J. Graph Theory93(1) (2020), 5-20. · Zbl 1495.05246 |
| [2] | R. E. L. Aldred, K. Kawarabayashi and M. D. Plummer, On the matching extendability of graphs in surfaces,J. Comb. Theory Ser. B98(2008), 105-115. · Zbl 1131.05031 |
| [3] | R. E. L. Aldred, Q. Li, M. D. Plummer, D. Ye and H. Zhang, Matching extension in toroidal quadrangulations II: the 3-extendable case,Australas. J. Combin.63 (2015), 268-295. · Zbl 1325.05133 |
| [4] | R. E. L. Aldred, Q. Li, M. D. Plummer and H. Zhang, Matching extension in quadrangulations of the torus,Australas. J. Combin.57(2013), 217-233. · Zbl 1293.05284 |
| [5] | R. E. L. Aldred and M. D. Plummer, Edge proximity and matching extension in planar triangulations,Australas. J. Combin.29(2004), 215-224. · Zbl 1048.05066 |
| [6] | R. E. L. Aldred and M. D. Plummer, Proximity thresholds for matching extension in planar and projective planar triangulations,J. Graph Theory67(1) (2011), 38-46. · Zbl 1230.05230 |
| [7] | R. E. L. Aldred and M. D. Plummer, Extendability and criticality in matching theory,Graphs Combin.36(2020), 573-589. · Zbl 1439.05182 |
| [8] | R. E. L. Aldred, M. D. Plummer and W. Ruksasakchai, Distance restricted matching extension missing vertices and edges in 5-connected triangulations of the plane,J. Graph Theory95(2) (2020), 240-255. · Zbl 1486.05238 |
| [9] | O. Chan, C. C. Chen and Q. L. Yu, On 2-extendable abelian Cayley graphs, Discrete Math.146(1995), 19-32. · Zbl 0837.05069 |
| [10] | S. M. Cioab˘a, J. Koolen and W. Li, Max-cut and extendability of matchings in distance-regular graphs,European J. Combin.62(2017), 232-244. · Zbl 1358.05083 |
| [11] | J. Fujisawa, K. Segawa and Y. Suzuki, The matching extendability of optimal 1-planar graphs,Graphs Combin.34(5) (2018), 1088-1099. · Zbl 1402.05045 |
| [12] | E. Gy¨ori and M. D. Plummer, The Cartesian product of ak-extendable and an l-extendable graph is (k+l+ 1)-extendable,Discrete Math.101(1-3) (1992), 87-96. · Zbl 0769.05075 |
| [13] | P. Hall, On representatives of subsets,J. London. Math. Soc.10(1) (1935), 26-30. · JFM 61.0067.01 |
| [14] | N. B. Limaye and D. G. Sarvate, Onr-extendability of the hypercubeQn,Math. Bohem.122(3) (1997), 249-255. · Zbl 0898.05057 |
| [15] | J. Liu, Hamiltonian decompositions of Cayley graphs on abelian groups,Discrete Math.131(1994), 163-171. · Zbl 0809.05058 |
| [16] | Y. Luo and X. Gao, On the extendability of bi-Cayley graphs of finite abelian groups,Discrete Math.309(20) (2009), 5943-5949. · Zbl 1198.05093 |
| [17] | M. D. Plummer, A theorem on matchings in the plane,Ann. Discrete Math.41 (1989), 347-354. · Zbl 0683.05033 |
| [18] | M. D. Plummer, Extending matchings in graphs: a survey,Discrete Math.127 (1994), 277-292. · Zbl 0798.05040 |
| [19] | M. D. Plummer, Extending matchings in graphs: an update,Congressus Numer. 116(1996), 3-32. · Zbl 0902.05059 |
| [20] | M. D. Plummer, Recent progress in matching extension,Building Bridges, Bolyai Soc. Math. Stud.19, Springer, Berlin, 2008, 427-454. · Zbl 1209.05189 |
| [21] | J. Vandenbussche and D. B. West, Matching extendability in hypercubes,SIAM J. Discrete Math.23(3) (2009), 1539-1547. · Zbl 1207.05161 |
| [22] | Wolfram Research, Inc.: Mathematica, Version 12.1. Champaign, IL (2020) |
| [23] | W. Zhang, Matching extendability and connectivity of regular graphs from eigenvalues,Graphs Combin.36(1) (2020), 93-108 · Zbl 1434.05083 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
