On the maximum number of maximum dissociation sets in trees with given dissociation number

被引：3
|
作者：
Tu, Jianhua [1 ]
Zhang, Lei [2 ]
Du, Junfeng [3 ]
机构：
[1] Beijing Technol & Business Univ, Sch Math & Stat, Beijing 100048, Peoples R China
[2] Beijing Inst Technol, Sch Math & Stat, Beijing 100081, Peoples R China
[3] Beijing Univ Chem Technol, Coll Math & Phys, Beijing 100029, Peoples R China
来源：
DISCRETE MATHEMATICS | 2024年 / 347卷 / 05期
基金：
北京市自然科学基金;
关键词：
Maximum dissociation set; Dissociation number; Tree; Extremal enumeration; 3-PATH VERTEX COVER; INDEPENDENT SETS; ENUMERATION; ALGORITHM;
D O I：
10.1016/j.disc.2024.113910
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
In a graph G, a subset of vertices is a dissociation set if it induces a subgraph with vertex degree at most 1. A maximum dissociation set is a dissociation set of maximum cardinality. The dissociation number of G, denoted by psi (G), is the cardinality of a maximum dissociation set of G. Extremal problems involving counting the number of a given type of substructure in a graph have been a hot topic of study in extremal graph theory throughout the last few decades. In this paper, we determine the maximum number of maximum dissociation sets in a tree with prescribed dissociation number and the extremal trees achieving this maximum value. (c) 2024 Elsevier B.V. All rights reserved.
引用
收藏
页数：10
相关论文
共 50 条
  • [31] The maximum number of connected sets in regular graphs
    Cambie, Stijn
    Goedgebeur, Jan
    Jooken, Jorik
    ELECTRONIC JOURNAL OF COMBINATORICS, 2025, 32 (01)
  • [32] The Maximum Number of Complete Subgraphs of Fixed Size in a Graph with Given Maximum Degree
    Cutler, Jonathan
    Radcliffe, A. J.
    JOURNAL OF GRAPH THEORY, 2017, 84 (02) : 134 - 145
  • [33] Trees with a given order and matching number that have maximum general sum-connectivity index
    Zhu, Zhongxun
    Zhang, Wei
    ARS COMBINATORIA, 2016, 128 : 439 - 446
  • [34] Maximization of the spectral radius of block graphs with a given dissociation number
    Das, Joyentanuj
    Mohanty, Sumit
    APPLIED MATHEMATICS AND COMPUTATION, 2024, 465
  • [35] On the minimum spectral radius of graphs with given order and dissociation number
    Zhao, Jing
    Liu, Huiqing
    Xiong, Jin
    DISCRETE APPLIED MATHEMATICS, 2025, 361 : 487 - 501
  • [36] Extremal vertex-degree function index with given order and dissociation number
    Huang, Jing
    Zhang, Huihui
    DISCRETE APPLIED MATHEMATICS, 2024, 342 : 142 - 152
  • [37] The distribution of the maximum protection number in simply generated trees
    Heuberger, Clemens
    Selkirk, Sarah J.
    Wagner, Stephan
    COMBINATORICS PROBABILITY & COMPUTING, 2024,
  • [38] An improvement on the maximum number of k-dominating independent sets
    Gerbner, Daniel
    Keszegh, Balazs
    Methuku, Abhishek
    Patkos, Balazs
    Vizer, Mate
    JOURNAL OF GRAPH THEORY, 2019, 91 (01) : 88 - 97
  • [39] Enumeration and maximum number of maximal irredundant sets for chordal graphs
    Golovach, Petr A.
    Kratsch, Dieter
    Liedloff, Mathieu
    Sayadi, Mohamed Yosri
    DISCRETE APPLIED MATHEMATICS, 2019, 265 (69-85) : 69 - 85
  • [40] Enumeration and maximum number of minimal dominating sets for chordal graphs
    Golovach, Petr A.
    Kratsch, Dieter
    Liedtoff, Mathieu
    Sayadi, Mohamed Yosri
    THEORETICAL COMPUTER SCIENCE, 2019, 783 : 41 - 52
12345