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

DOI10.1016/J.DISC.2024.113910MaRDI QIDQ6204327zbMATH OpenOpenAlexFDO

Authors Jianhua Tu, Lei Zhang, Junfeng Du

Publication date 27 March 2024

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2103.01407

zbMATH Keywords

dissociation numberextremal enumerationmaximum dissociation settree

Mathematics Subject Classification ID

Trees (05C05) Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35)

Abstract: 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.

Recommendations

• Minimum number of maximal dissociation sets in trees
• Maximum dissociation sets in subcubic trees
• On the maximal number of maximum dissociation sets in forests with fixed order and dissociation number
• Maximal and maximum dissociation sets in general and triangle-free graphs
• The maximum number of maximum dissociation sets in trees

Cites work

• A faster FPT algorithm for 3-path vertex cover
• A Note on Independent Sets in Trees
• A primal-dual approximation algorithm for the vertex cover P^3 problem
• Bounds on the maximum number of minimum dominating sets
• Enumeration and maximum number of minimal connected vertex covers in graphs
• Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
• Graph theory
• Independent packings in structured graphs
• Many cliques with few edges
• Maximal and maximum independent sets in graphs with at mostr cycles
• Maximal independent sets in bipartite graphs
• Maximizing the number of independent sets of a fixed size
• Maximum Number of Minimal Feedback Vertex Sets in Chordal Graphs and Cographs
• Minimum \(k\)-path vertex cover
• Node-Deletion Problems on Bipartite Graphs
• NP-hard graph problems and boundary classes of graphs
• On cliques in graphs
• On computing the minimum 3-path vertex cover and dissociation number of graphs
• On the maximum number of maximum independent sets
• On the maximum number of maximum independent sets in connected graphs
• On the maximum number of minimum dominating sets in forests
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• The complexity of dissociation set problems in graphs
• The maximum number of maximal independent sets in unicyclic connected graphs
• The maximum number of maximum dissociation sets in trees
• The maximum number of triangles in a graph of given maximum degree
• The number of independent sets in an irregular graph
• The number of maximal independent sets in a connected graph
• The Number of Maximal Independent Sets in a Tree
• The number of maximal independent sets in connected graphs
• The number of maximal independent sets in connected triangle-free graphs
• The number of maximum independent sets in graphs
• The structure and maximum number of maximum independent sets in trees

Cited in

(14)

• Maximum dissociation sets in subcubic trees
• Extremal vertex-degree function index with given order and dissociation number
• On spectral extrema of graphs with given order and dissociation number
• Minimum number of maximal dissociation sets in trees
• Enumerating maximal dissociation sets in three classes of grid graphs
• On the A_-index of graphs with given order and dissociation number
• Maximum generalized 4-independent sets in subcubic trees
• A note on the second-largest number of dissociation sets in connected graphs
• The characterization of the lower bound on the dissociation number of trees
• The maximum number of maximum dissociation sets in potted graphs
• Dissociation in circulant graphs and integer distance graphs
• On spectral extrema of graphs with given order and generalized 4-independence number
• Bounds on the dissociation number of unicyclic graphs
• The number of maximum dissociation sets in trees

This page was built for publication: On the maximum number of maximum dissociation sets in trees with given dissociation number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6204327)