On the maximal number of maximum dissociation sets in forests with fixed order and dissociation number

DOI10.11650/TJM/230204MaRDI QIDQ6178795zbMATH OpenOpenAlexWikidataFDO

Authors Wanting Sun, Shuchao Li

Publication date 5 September 2023

Published in Taiwanese Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://projecteuclid.org/journals/taiwanese-journal-of-mathematics/volume-27/issue-4/On-the-Maximal-Number-of-Maximum-Dissociation-Sets-in-Forests/10.11650/tjm/230204.full

zbMATH Keywords

dissociation numberdissociation setforesttree

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75)

Recommendations

• The maximum number of maximum dissociation sets in trees
• Maximal and maximum dissociation sets in general and triangle-free graphs
• A bound on the dissociation number
• Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree
• Complexity of dissociate set problems in some hereditary classes of graphs

Cites work

• An improved algorithm for the vertex cover \(P_3\) problem on graphs of bounded treewidth
• Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
• Graphs with the second largest number of maximal independent sets
• scientific article; zbMATH DE number 5995277 (Why is no real title available?)
• scientific article; zbMATH DE number 3717357 (Why is no real title available?)
• scientific article; zbMATH DE number 2192124 (Why is no real title available?)
• scientific article; zbMATH DE number 6257565 (Why is no real title available?)
• Independent packings in structured graphs
• Maximal and maximum independent sets in graphs with at mostr cycles
• Maximal independent sets in bipartite graphs
• Maximal independent sets in caterpillar graphs
• Maximal independent sets in graphs with at mostr cycles
• Maximal independent sets in minimum colorings
• Maximizing the number of independent sets of fixed size in connected graphs with given independence number
• 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 graphs with the third largest number of maximal independent sets
• 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
• The complexity of dissociation set problems in graphs
• The complexity of restricted spanning tree problems
• The maximum number of maximum dissociation sets in trees
• The number of maximum independent sets in graphs
• The structure and maximum number of maximum independent sets in trees
• Trees with the second and third largest number of maximal independent sets
• Trees with the second largest number of maximal independent sets

Cited in

(23)

• Maximal and maximum dissociation sets in general and triangle-free graphs
• Uniformly dissociated graphs
• A bound on the dissociation number
• The maximum number of maximum dissociation sets in trees
• 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
• On the maximum number of maximum dissociation sets in trees with given dissociation number
• 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
• A sharp lower bound on the generalized 4-independence number
• The minimum number of maximal dissociation sets in unicyclic graphs
• The maximum number of maximum dissociation sets in potted graphs
• The number of maximal dissociation sets in unicyclic graphs
• Maximal and maximum induced matchings in connected graphs
• The number of dissociation sets in connected graphs
• Upper bound for the number of maximal dissociation sets in trees
• On spectral extrema of graphs with given order and generalized 4-independence number
• On the Wiener index of graphs with given dissociation number

This page was built for publication: On the maximal number of maximum dissociation sets in forests with fixed order and dissociation number

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