Distance matching extension and local structure of graphs
Robert E. L. Aldred, Jun Fujisawa, Akira Saito · Journal of Graph Theory · 2019
Abstract A matching in a graph is said to be extendable if there exists a perfect matching of containing . Also, is said to be a distance matching if the shortest distance between a pair of edges in is at least . A graph is distance matchable if every distance matching is extendable in , regardless of its size. In this paper, we study the class of distance matchable graphs. In particular, we prove that for every integer with , there exists a positive integer such that every connected, locally ‐connected ‐free graph of even order is distance matchable. We also prove that every connected, locally ‐connected ‐free graph of even order is distance matchable. Furthermore, we make more detailed analysis of ‐free graphs and study their distance matching extension properties.