Extensions of barrier sets to nonzero roots of the matching polynomial

被引：8
|
作者：
Ku, Cheng Yeaw [1 ]
Wong, Kok Bin [2 ]
机构：
[1] Natl Univ Singapore, Dept Math, Singapore 117543, Singapore
[2] Univ Malaya, Inst Math Sci, Kuala Lumpur 50603, Malaysia
来源：
DISCRETE MATHEMATICS | 2010年 / 310卷 / 24期
关键词：
Matching polynomial; Gallai-Edmonds decomposition; Barrier sets; Extreme sets;
D O I：
10.1016/j.disc.2010.09.002
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
In matching theory, barrier sets (also known as Tutte sets) have been studied extensively due to their connection to maximum matchings in a graph. For a root theta of the matching polynomial, we define theta-barrier and theta-extreme sets. We prove a generalized Berge-Tutte formula and give a characterization for the set of all theta-special vertices in a graph. (C) 2010 Elsevier B.V. All rights reserved.
引用
收藏
页码：3544 / 3550
页数：7
相关论文
共 23 条
  • [11] Graphs With Few Matching Roots
    Ghorbani, Ebrahim
    GRAPHS AND COMBINATORICS, 2013, 29 (05) : 1377 - 1389
  • [12] Graphs With Few Matching Roots
    Ebrahim Ghorbani
    Graphs and Combinatorics, 2013, 29 : 1377 - 1389
  • [13] Gallai-Edmonds structure theorem for weighted matching polynomial
    Ku, Cheng Yeaw
    Wong, Kok Bin
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2013, 439 (11) : 3387 - 3411
  • [14] Graphs with integer matching polynomial zeros
    Akbari, S.
    Csikvari, P.
    Ghafari, A.
    Ghezelahmad, S. Khalashi
    Nahvi, M.
    DISCRETE APPLIED MATHEMATICS, 2017, 224 : 1 - 8
  • [15] Graphs with six distinct matching roots
    Zhang, Hailiang
    Yu, Guanglong
    Li, Shanlin
    INFORMATION PROCESSING LETTERS, 2015, 115 (05) : 521 - 526
  • [16] On the largest matching roots of graphs with cut edges
    Zhang, Hailiang
    INFORMATION PROCESSING LETTERS, 2018, 136 : 41 - 43
  • [17] Combinatorial explanation of coefficients of the Laplacian matching polynomial of graphs
    Li, Danyi
    Yan, Weigen
    DISCRETE MATHEMATICS, 2022, 345 (05)
  • [18] The matching polynomial of the path-tree of a complete graph
    Guo, Mingxu
    Chen, Haiyan
    DISCRETE APPLIED MATHEMATICS, 2024, 359 : 244 - 249
  • [19] On the largest matching roots of graphs with a given number of pendent vertices
    Zhang, Hailiang
    Chen, Guangting
    Yu, Guanglong
    DISCRETE APPLIED MATHEMATICS, 2019, 255 : 339 - 344
  • [20] Laplacian coefficient, matching polynomial and incidence energy of trees with described maximum degree
    Ya-Lei Jin
    Yeong-Nan Yeh
    Xiao-Dong Zhang
    Journal of Combinatorial Optimization, 2016, 31 : 1345 - 1372
123