Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree

DOI10.3934/math.2022036zbMath1485.05174arXiv2102.12053OpenAlexW3206805497MaRDI QIDQ2129757

Rongling Lang, Lei Zhang, Jian-hua Tu, Jun-feng Du

Publication date: 25 April 2022

Published in: AIMS Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

treepolynomial time algorithmindependent setmaximum dissociation set

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
• A faster FPT algorithm for 3-path vertex cover
• Vertices contained in all or in no minimum total dominating set of a tree
• On the vertices belonging to all, some, none minimum dominating set
• Minimum \(k\)-path vertex cover
• The complexity of dissociation set problems in graphs
• NP-hard graph problems and boundary classes of graphs
• Vertices belonging to all or to no minimum double dominating sets in trees
• Independent packings in structured graphs
• Improper coloring of unit disk graphs
• Node-Deletion Problems on Bipartite Graphs
• The complexity of restricted spanning tree problems
• Vertices Belonging to All or to No Maximum Stable Sets of a Graph
• Vertices contained in every minimum dominating set of a tree
• The maximum number of maximum dissociation sets in trees

This page was built for publication: Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree