Maximal and maximum dissociation sets in general and triangle-free graphs

DOI10.1016/j.amc.2022.127107OpenAlexW3133679593WikidataQ114210900 ScholiaQ114210900MaRDI QIDQ2141169

Jun-feng Du, Jian-hua Tu, Yu-Xin Li

Publication date: 23 May 2022

Published in: Applied Mathematics and Computation (Search for Journal in Brave)

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

zbMATH Keywords

extremal graphstriangle-free graphsgeneral graphsmaximal dissociation sets

Mathematics Subject Classification ID

Theory of computing (68Qxx) Graph theory (05Cxx) Discrete mathematics in relation to computer science (68Rxx)

Related Items (4)

Relating the independence number and the dissociation number ⋮ Maximum weight t-sparse set problem on vector-weighted graphs ⋮ Extremal vertex-degree function index with given order and dissociation number ⋮ Minimum number of maximal dissociation sets in trees

Cites Work

• Bounds on the maximum number of minimum dominating sets
• Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
• On computing the minimum 3-path vertex cover and dissociation number of graphs
• The maximum number of maximal independent sets in unicyclic connected graphs
• Trees with extremal numbers of maximal independent sets including the set of leaves
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• The number of maximal independent sets in a connected graph
• Enumeration and maximum number of minimal connected vertex covers in graphs
• On the maximum number of minimum dominating sets in forests
• On the maximum number of maximum independent sets
• The complexity of dissociation set problems in graphs
• Maximum Number of Minimal Feedback Vertex Sets in Chordal Graphs and Cographs
• Maximal independent sets in bipartite graphs
• Maximal and maximum independent sets in graphs with at mostr cycles
• The Number of Maximal Independent Sets in a Tree
• A Note on Independent Sets in Trees
• The number of maximal independent sets in connected graphs
• Node-Deletion Problems on Bipartite Graphs
• The structure and maximum number of maximum independent sets in trees
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• Feedback Vertex Sets in Tournaments
• Maximal Induced Matchings in Triangle-Free Graphs
• Algorithms and Computation
• On cliques in graphs
• The number of maximum independent sets in graphs
• The maximum number of maximum dissociation sets in trees
• On the maximum number of maximum independent sets in connected graphs

This page was built for publication: Maximal and maximum dissociation sets in general and triangle-free graphs