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

Jianhua Tu, Lei Zhang, Junfeng Du

Published 2021-02-24Version 1

Given a graph G, a subset of vertices is called a maximum dissociation set if it induces a subgraph of maximum degree at most 1 and the subset has maximum cardinality. In this paper, we first characterize the set of vertices of a tree that are contained in all, or in no, maximum dissociation sets of the tree. Then we present a linear time recognition algorithm which can determine whether a given vertex in a tree is in all (or no) maximum dissociation sets of the tree. Thus we can find all vertices contained in all (or no) maximum dissociation sets of a tree of order n in O(n2) time.