Fractional matchings on regular graphs

被引:0
作者
Guan, Xiaxia [1 ]
Ma, Tianlong [2 ,3 ]
机构
[1] Taiyuan Univ Technol, Dept Math, Taiyuan, Peoples R China
[2] Jimei Univ, Sch Sci, Xiamen, Peoples R China
[3] Xiamen Univ, Sch Math Sci, Xiamen, Peoples R China
关键词
Fractional matching number; Fractional perfect matching; Regular graph; Edge-connectivity; PRECLUSION; CONNECTIVITY;
D O I
10.1007/s11227-024-06206-6
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
Every k-regular graph has a fractional perfect matching via assigning each edge a fractional number 1/k. How many edges are deleted from a regular graph so that the resulting graph still has a fractional perfect matching? Let G be a k-regular graph with n vertices. In this paper, we prove that the fractional matching number of the resulting graph deleting any (sic)(t+1)k-1/2(sic) edges from G is not less than 1/2(n - t). In particular, taking t = 0, we deduce that the resulting graph deleting any (sic)k-1/2(sic) edges from G has a fractional perfect matching. Specially, we can delete any k - 1 edges from G other than exceptions such that the resulting graph has a fractional perfect matching when n <= 2k - 2. Further, the resulting graph deleting any (sic)k+l-1/2(sic) edges from a k-regular l-edge-connected graph with an even number of vertices has a fractional perfect matching. As applications, some values or bounds on the fractional matching preclusion number of regular graphs are deduced immediately.
引用
收藏
页码:18942 / 18953
页数:12
相关论文
共 50 条
  • [21] 1/n Expansion for the Number of Matchings on Regular Graphs and Monomer-Dimer Entropy
    Pernici, Mario
    JOURNAL OF STATISTICAL PHYSICS, 2017, 168 (03) : 666 - 679
  • [22] Balloons, Cut-Edges, Matchings, and Total Domination in Regular Graphs of Odd Degree
    Suil, O.
    West, Douglas B.
    JOURNAL OF GRAPH THEORY, 2010, 64 (02) : 116 - 131
  • [23] 1 / n Expansion for the Number of Matchings on Regular Graphs and Monomer-Dimer Entropy
    Mario Pernici
    Journal of Statistical Physics, 2017, 168 : 666 - 679
  • [24] A Note on Connectivity of Regular Graphs
    Xu, Huixian
    Zhou, Jinqiu
    JOURNAL OF INTERCONNECTION NETWORKS, 2023, 23 (04)
  • [25] Perfect matchings in random intersection graphs
    Mindaugas Bloznelis
    Tomasz Łuczak
    Acta Mathematica Hungarica, 2013, 138 : 15 - 33
  • [26] Matchings in graphs from the spectral radius
    Kim, Minjae
    Suil, O.
    Sim, Wooyong
    Shin, Dongwoo
    LINEAR & MULTILINEAR ALGEBRA, 2023, 71 (11) : 1794 - 1803
  • [27] Matchings in graphs of odd regularity and girth
    Costa, Vitor
    Dantas, Simone
    Rautenbach, Dieter
    DISCRETE MATHEMATICS, 2013, 313 (24) : 2895 - 2902
  • [28] Perfect matchings in random intersection graphs
    Bloznelis, M.
    Luczak, T.
    ACTA MATHEMATICA HUNGARICA, 2013, 138 (1-2) : 15 - 33
  • [29] Integer k-matchings of graphs
    Liu, Yan
    Liu, Xiaohui
    DISCRETE APPLIED MATHEMATICS, 2018, 235 : 118 - 128
  • [30] Regular factors of simple regular graphs and factor-spectra
    Niessen, T
    Randerath, B
    DISCRETE MATHEMATICS, 1998, 185 (1-3) : 89 - 103