Distance matching extension in cubic bipartite graphs

DOI10.1007/S00373-021-02295-9MaRDI QIDQ2051886zbMATH OpenOpenAlexFDO

Authors Jun Fujisawa, Akira Saito, R. E. L. Aldred

Publication date 25 November 2021

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00373-021-02295-9

cubic bipartite graphs distance restricted matching extension planar graphs projective planar graphs

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

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}

Recommendations

Cites work

Cited in

(5)

This page was built for publication: Distance matching extension in cubic bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2051886)