Closed formulas for the numbers of small independent sets and matchings and an extremal problem for trees

被引：15
作者：
Delorme, C
Favaron, O
Rautenbach, D
机构：
[1] Univ Bonn, Forsch Inst Diskrete Math, D-53113 Bonn, Germany
[2] Univ Paris 11, Rech Informat Lab, F-91405 Orsay, France
来源：
DISCRETE APPLIED MATHEMATICS | 2003年 / 130卷 / 03期
关键词：
independent set; matching; degree sequence; tree; Kruskal's algorithm;
D O I：
10.1016/S0166-218X(03)00328-7
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
We derive closed formulas for the numbers of independent sets of size at most 4 and matchings of size at most 3 in graphs without small cycles that depend only on the degree sequence and the products of the degrees of adjacent vertices. As a related problem we describe an algorithm that determines a tree of given degree sequence that maximizes the sum of the products of the degrees of adjacent vertices. (C) 2003 Elsevier B.V. All rights reserved.
引用
收藏
页码：503 / 512
页数：10
相关论文
共 16 条
  • [1] [Anonymous], GRAPH THEORY NOTES N
  • [2] [Anonymous], 1979, MATCH-COMMUN MATH CO
  • [3] BEEZER RA, 1996, B I COMBIN APPL, V18, P17
  • [4] Extremal graphs for weights
    Bollobás, B
    Erdos, P
    Sarkar, A
    [J]. DISCRETE MATHEMATICS, 1999, 200 (1-3) : 5 - 19
  • [5] Bollobás B, 1998, ARS COMBINATORIA, V50, P225
  • [6] On the Randic index
    Delorme, C
    Favaron, O
    Rautenbach, D
    [J]. DISCRETE MATHEMATICS, 2002, 257 (01) : 29 - 38
  • [7] ON MATCHING COEFFICIENTS
    FARRELL, EJ
    GUO, JM
    CONSTANTINE, GM
    [J]. DISCRETE MATHEMATICS, 1991, 89 (02) : 203 - 210
  • [8] INTRODUCTION TO MATCHING POLYNOMIALS
    FARRELL, EJ
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1979, 27 (01) : 75 - 86
  • [9] FISCHERMAN M, 2001, UNPUB NOTE NUMBER MA
  • [10] A linear-programming approach to the generalized Randic index
    Fischermann, M
    Hoffmann, A
    Rautenbach, D
    Volkmann, L
    [J]. DISCRETE APPLIED MATHEMATICS, 2003, 128 (2-3) : 375 - 385
12