Enumerating maximal dissociation sets in three classes of grid graphs

DOI10.1016/j.amc.2024.128711zbMATH Open1545.05108MaRDI QIDQ6585552

Jianhua Tu, Yuting Tian

Publication date: 12 August 2024

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

zbMATH Keywords

enumerationgrid graphsmaximal dissociation setsstate matrix recursion algorithm

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Enumerating independent vertex sets in grid graphs
• 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
• The number of maximal independent sets in a connected graph
• A matrix method for counting Hamiltonian cycles on grid graphs
• The number of Hamiltonian paths in a rectangular grid
• On the distribution of roots of algebraic equations with integral coefficients
• State matrix recursion method and monomer-dimer problem
• Number of dominating sets in cylindric square grid graphs
• Maximal and maximum dissociation sets in general and triangle-free graphs
• The complexity of dissociation set problems in graphs
• Maximal independent sets on a grid graph
• Maximal independent sets in graphs with at mostr cycles
• The Number of Maximal Independent Sets in a Tree
• The number of maximal independent sets in connected graphs
• Node-Deletion Problems on Bipartite Graphs
• The Number of Independent Sets in a Grid Graph
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• On cliques in graphs
• A bound on the dissociation number
• The maximum number of maximum dissociation sets in trees
• Relating the independence number and the dissociation number
• Maximum dissociation sets in subcubic trees
• On the maximal number of maximum dissociation sets in forests with fixed order and dissociation number

This page was built for publication: Enumerating maximal dissociation sets in three classes of grid graphs

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