\(4\)-Regular Bipartite Matching Extendable Graphs

Abstract

Let \(G\) be a simple connected graph containing a perfect matching.
\(G\) is said to be BM-extendable (bipartite matching extendable)
if every matching \(M\) which is a perfect matching of an induced
bipartite subgraph of \(G\) extends to a perfect matching of \(G\).

The BM-extendable cubic graphs are known to be \(K_{4}\) and \(K_{3,3}\).
In this paper, we characterize the 4-regular BM-extendable graphs.
We show that the only 4-regular BM-extendable graphs are \(K_{4,4}\) and
\(T_{4n}\), \(n \geq 2\), where \(T_{4n}\) is the graph on \(4n\) vertices
\(u_{i}\), \(v_{i}\), \(x_{i}\), \(y_{i}\), \(1 \leq i \leq n\), such that
\(\{u_{i}, v_{i}, x_{i}, y_{i}\}\) is a clique and
\(x_{i}u_{i+1}\), \(y_{i}v_{i+1} \in E(T_{4n})\) (mod \(n\)).