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

DOI10.3934/MATH.2022036MaRDI QIDQ2129757zbMATH OpenOpenAlexFDO

Authors Lei Zhang, Rongling Lang, Jianhua Tu, Junfeng Du

Publication date 25 April 2022

Published in AIMS Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

treeindependent setpolynomial time algorithmmaximum 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)

Abstract: In a graph G, a dissociation set is a subset of vertices which induces a subgraph with vertex degree at most 1. Finding a dissociation set of maximum cardinality in a graph is NP-hard even for bipartite graphs and is called the maximum dissociation set problem. The complexity of maximum dissociation set problem in various subclasses of graphs has been extensively studied in the literature. In this paper, we study the maximum dissociation problem from different perspectives and characterize the vertices belonging to all maximum dissociation sets, and to no maximum dissociation set of a tree. We present a linear time recognition algorithm which can determine whether a given vertex in a tree is contained in all (or no) maximum dissociation sets of the tree. Thus for a tree with n vertices, we can find all vertices belonging to all (or no) maximum dissociation sets of the tree in O(n^2) time.

Recommendations

• Maximum dissociation sets in subcubic trees
• The maximum number of maximum dissociation sets in trees
• A polynomial time algorithm recognizing link trees
• Finding the maximum common subgraph of a partial \(k\)-tree and a graph with a polynomially bounded number of spanning trees
• Algorithms and Computation
• Vertices contained in all or in no minimum disjunctive dominating set of a tree
• Vertices contained in all or in no minimum \(k\)-dominating sets of a tree
• Recognizing vertex intersection graphs of paths on bounded degree trees
• Polynomial algorithms to finite Veber problem for a tree network
• Polynomial time algorithms for variants of graph matching on partial k-trees

Cites work

• scientific article; zbMATH DE number 2192124 (Why is no real title available?)
• A faster FPT algorithm for 3-path vertex cover
• A primal-dual approximation algorithm for the vertex cover P^3 problem
• Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
• Graph theory
• Improper coloring of unit disk graphs
• Independent packings in structured graphs
• Minimum \(k\)-path vertex cover
• NP-hard graph problems and boundary classes of graphs
• Node-Deletion Problems on Bipartite Graphs
• On computing the minimum 3-path vertex cover and dissociation number of graphs
• On the vertices belonging to all, some, none minimum dominating set
• The complexity of dissociation set problems in graphs
• The complexity of restricted spanning tree problems
• The maximum number of maximum dissociation sets in trees
• Vertices Belonging to All or to No Maximum Stable Sets of a Graph
• Vertices belonging to all or to no minimum double dominating sets in trees
• Vertices contained in all or in no minimum total dominating set of a tree
• Vertices contained in every minimum dominating set of a tree

Cited in

(4)

• The maximum number of maximum dissociation sets in trees
• Faster computation of the maximum dissociation set and minimum 3-path vertex cover in graphs
• On the maximal number of maximum dissociation sets in forests with fixed order and dissociation number
• Complexity of dissociate set problems in some hereditary classes of graphs

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

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