Distance matching extension in cubic bipartite graphs (Q2051886): Difference between revisions
From MaRDI portal
Latest revision as of 08:16, 27 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Distance matching extension in cubic bipartite graphs |
scientific article |
Statements
Distance matching extension in cubic bipartite graphs (English)
0 references
25 November 2021
0 references
A graph \(G\) is said to be distance \(d\) matchable if, for any matching \(M\) of \(G\) in which edges are pairwise at least distance \(d\) apart, there exists a perfect matching \(M^\ast\) of \(G\) which contains \(M\). The authors of this article prove the following results: \begin{itemize} \item[(1)] if \(G\) is a cubic bipartite graph in which, for each \(e \in E(G)\), there exist two cycles \(C_1\), \(C_2\) of length at most \(d\) such that \(E(C_1)\cap E(C_2)=\{e\}\), then \(G\) is distance \(d - 1\) matchable. \item[(2)] if \(G\) is a planar or projective planar cubic bipartite graph in which, for each \(e\in E(G)\), there exist two cycles \(C_1\), \(C_2\) of length at most \(6\) such that \(e\in E(C_1)\cap E(C_2)\), then \(G\) is distance \(6\) matchable. \end{itemize}
0 references
distance restricted matching extension
0 references
cubic bipartite graphs
0 references
planar graphs
0 references
projective planar graphs
0 references
0 references
0 references