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

DOI10.3934/MATH.2022036zbMATH Open1485.05174arXiv2102.12053OpenAlexW3206805497MaRDI QIDQ2129757FDOQ2129757

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

Publication date: 25 April 2022

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

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.

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

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

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)

Cites Work

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

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)