Distance matching extension and local structure of graphs

被引：4

作者：

Aldred, R. E. L. ^{[1
]}

Fujisawa, Jun ^{[2
]}

Saito, Akira ^{[3
]}

机构：

[1] Univ Otago, Dept Math & Stat, Dunedin, New Zealand

[2] Keio Univ, Fac Business & Commerce, Kohoku Ku, Hiyoshi 4-1-1, Yokohama, Kanagawa 2238521, Japan

[3] Nihon Univ, Dept Informat Sci, Setagaya Ku, Tokyo, Japan

来源：

JOURNAL OF GRAPH THEORY | 2020年 / 93卷 / 01期

基金：

日本学术振兴会;

关键词：

distance restricted matching extension; local connectivity; star-free;

D O I：

10.1002/jgt.22465

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A matching M in a graph G is said to be extendable if there exists a perfect matching of G containing M. Also, M is said to be a distance d matching if the shortest distance between a pair of edges in M is at least d. A graph G is distance d matchable if every distance d matching is extendable in G, regardless of its size. In this paper, we study the class of distance d matchable graphs. In particular, we prove that for every integer k with k >= 3, there exists a positive integer d such that every connected, locally (k - 1)-connected K-1,K-k-free graph of even order is distance d matchable. We also prove that every connected, locally k-connected K-1,K-k-free graph of even order is distance 3 matchable. Furthermore, we make more detailed analysis of K1,4-free graphs and study their distance matching extension properties.

引用

页码：5 / 20

页数：16

共 12 条

[1] Proximity Thresholds for Matching Extension in Planar and Projective Planar Triangulations [J].