Enumerating maximal dissociation sets in three classes of grid graphs

DOI10.1016/j.amc.2024.128711MaRDI QIDQ6585552zbMATH OpenFDO

Authors Yuting Tian, Jianhua Tu

Publication date 12 August 2024

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

Full work available at URL https://doi.org/10.1016/j.amc.2024.128711

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)

Recommendations

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

Cites work

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

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)