Fractional matching preclusion numbers of Cartesian product graphs

被引:1
|
作者
Luan, Yu [1 ]
Lu, Mei [1 ]
Zhang, Yi [2 ]
机构
[1] Tsinghua Univ, Dept Math Sci, Beijing 100084, Peoples R China
[2] Beijing Univ Posts & Telecommun, Sch Sci, Beijing 100876, Peoples R China
基金
中国国家自然科学基金;
关键词
Available online xxxx; Fractional matching preclusion number; Cartesian product; Path; Cycle;
D O I
10.1016/j.dam.2023.05.021
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
The Cartesian product of two simple graphs G and H is the graph G ❑ H whose vertex set is V (G) x V(H) and whose edge set is the set of all pairs (u1, v1)(u2, v2) such that either u1u2 E E(G) and v1 = v2, or v1v2 E E(H) and u1 = u2. The fractional matching preclusion number of a graph G, denoted by fmp(G), is the minimum number of edges whose deletion results in a graph with no fractional perfect matching. In this paper, we determine fmp(G ❑ H) when H is a cycle or a path of even order; Moreover, given any integers a, b with a > 1 and 0 < b < a + 1, we construct a graph G such that & delta;(G) = a and fmp(G ❑ H) = b when H is a path of odd order.& COPY; 2023 Elsevier B.V. All rights reserved.
引用
收藏
页码:100 / 112
页数:13
相关论文
共 50 条
  • [1] Conditional matching preclusion for regular bipartite graphs and their Cartesian product
    Lin, Ruizhi
    DISCRETE APPLIED MATHEMATICS, 2021, 299 : 17 - 25
  • [2] Matching Preclusion Number in Cartesian Product of Graphs and its Application to Interconnection Networks
    de Almeida, Aline Ribeiro
    Protti, Fabio
    Markenzon, Lilian
    ARS COMBINATORIA, 2013, 112 : 193 - 204
  • [3] Fractional matching preclusion number of graphs?
    Zou, Jinyu
    Mao, Yaping
    Wang, Zhao
    Cheng, Eddie
    DISCRETE APPLIED MATHEMATICS, 2022, 311 : 142 - 153
  • [4] Matching preclusion number in product graphs
    Wang, Zhao
    Melekian, Christopher
    Cheng, Eddie
    Mao, Yaping
    THEORETICAL COMPUTER SCIENCE, 2019, 755 : 38 - 47
  • [5] Fractional matching preclusion of product networks
    Wang, Jinling
    THEORETICAL COMPUTER SCIENCE, 2020, 846 : 75 - 81
  • [6] Certain domination numbers for Cartesian product of graphs
    Arulanand, S.
    Rajan, R. Sundara
    Prabhu, S.
    Stephen, Sudeep
    JOURNAL OF DISCRETE MATHEMATICAL SCIENCES & CRYPTOGRAPHY, 2024, 27 (03) : 1045 - 1058
  • [7] Fractional matching preclusion of the restricted HL-graphs
    Shunzhe Zhang
    Huiqing Liu
    Dong Li
    Xiaolan Hu
    Journal of Combinatorial Optimization, 2019, 38 : 1143 - 1154
  • [8] Fractional matching preclusion of the restricted HL-graphs
    Zhang, Shunzhe
    Liu, Huiqing
    Li, Dong
    Hu, Xiaolan
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2019, 38 (04) : 1143 - 1154
  • [9] Matching preclusion and conditional matching preclusion problems for tori and related Cartesian products
    Cheng, Eddie
    Liptak, Laszlo
    DISCRETE APPLIED MATHEMATICS, 2012, 160 (12) : 1699 - 1716
  • [10] Panconnectivity of Cartesian product graphs
    Lu, You
    Xu, Jun-Ming
    JOURNAL OF SUPERCOMPUTING, 2011, 56 (02) : 182 - 189