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 条
  • [1] Generalized D-graphs for nonzero roots of the matching polynomial
    Ku, Cheng Yeaw
    Wong, Kok Bin
    DISCRETE MATHEMATICS, 2011, 311 (20) : 2174 - 2186
  • [2] Application of the Maximum Real Roots of Matching Polynomial
    Qiao, Youfu
    Zhan, Fuqin
    INFORMATION COMPUTING AND APPLICATIONS, 2011, 7030 : 105 - 112
  • [3] Polynomial reconstruction of the matching polynomial
    Li, Xueliang
    Shi, Yongtang
    Trinks, Martin
    ELECTRONIC JOURNAL OF GRAPH THEORY AND APPLICATIONS, 2015, 3 (01) : 27 - 34
  • [4] An analogue of the Gallai-Edmonds Structure Theorem for non-zero roots of the matching polynomial
    Ku, Cheng Yeaw
    Chen, William
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2010, 100 (02) : 119 - 127
  • [5] ON THE MATCHING POLYNOMIAL OF A POLYGRAPH
    BROERSMA, HJ
    LI, XL
    DISCRETE APPLIED MATHEMATICS, 1993, 46 (01) : 79 - 86
  • [6] Independence polynomial and matching polynomial of the Koch network
    Liao, Yunhua
    Xie, Xiaoliang
    INTERNATIONAL JOURNAL OF MODERN PHYSICS B, 2015, 29 (32):
  • [7] More connections between the matching polynomial and the chromatic polynomial
    Carely Luna-Olivera, Beatriz
    Merino, Criel
    Ramirez-Ibanez, Marcelino
    AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2019, 16 (03) : 319 - 323
  • [8] On the matching polynomial of subdivision graphs
    Yan, Weigen
    Yeh, Yeong-Nan
    DISCRETE APPLIED MATHEMATICS, 2009, 157 (01) : 195 - 200
  • [9] On the matching polynomial of theta graphs
    Zhang, Hailiang
    Shu, Jinlong
    ARS COMBINATORIA, 2012, 105 : 477 - 490
  • [10] On Vertex Matching Polynomial of Graphs
    Fath-Tabar, G. H.
    Loghman, A.
    ARS COMBINATORIA, 2012, 104 : 375 - 384
123