@techreport{TR-IC-25-02,
   number = {IC-25-02},
   author = {A. A. {Pereira} and C. N. {Campos}},
   title = {{Matching extendability in cartesian product of hypercubes
                   and paths}},
   month = {October},
   year = {2025},
   institution = {Institute of Computing, University of Campinas},
   note = {In English, 08 pages.
    \par\selectlanguage{english}\textbf{Abstract}
       A  matching  $M$  in  a graph $G$ is said to be extendable to a
       perfect  matching  if  there exists a perfect matching $M^*$ of
       $G$  such  that  $M  \subseteq M^*$. In this work, we study the
       extendability  of matchings under a neighbourhood condition: no
       unsaturated  vertex  has  all  of its neighbours $M$-saturated.
       Vandenbussche and West showed that, in the hypercube $Q_n$, any
       matching  of  size  at most $2n - 4$ is extendable to a perfect
       matching  if and only if it satisfies this condition. We extend
       their result to the cartesian product $Q_n \ \square \ P_m$, by
       proving  that  every  matching  of  size  at  most  $2n - 2$ is
       extendable  to  a  perfect  matching if and only if it does not
       saturate   the   neighbourhood   of   any  unsaturated  vertex. 
       Furthermore,  we  demonstrate  that  this  bound  is  tight  by 
       constructing a matching of size $2n + 2\delta(H) - 3$ in $Q_n \
       \square  \ H$ that satisfies the neighbourhood condition but is
       not extendable to a perfect matching.
  }
}