{
  "id": "2102.12053",
  "version": "v1",
  "published": "2021-02-24T03:53:00.000Z",
  "updated": "2021-02-24T03:53:00.000Z",
  "title": "Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree",
  "authors": [
    "Jianhua Tu",
    "Lei Zhang",
    "Junfeng Du"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-02-24T03:53:00.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "maximum dissociation set",
      "polynomial time recognition",
      "linear time recognition algorithm",
      "maximum degree",
      "maximum cardinality"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}