A clique cut-set in a connected graph is a clique whose deletion results in a disconnected graph. A graph is an atom if it has no clique cut-set. There are many computational problems that are polynomial-time solvable on a hereditary graph class \(\mathcal {G}\) whenever they are polynomial-time solvable on the atoms in  \(\mathcal {G}\) . A simplicial vertex is one whose neighbourhood is a clique. If an atom is not a complete graph, then it cannot contain any simplicial vertices. Conversely, in many hereditary classes \(\mathcal {G}\) , we find that if a graph in \(\mathcal {G}\) does not contain any simplicial vertices, then it must be an atom. In this paper, we investigate the boundary between avoiding simplicial vertices and being an atom. We fully describe all minimal graphs without simplicial vertices that are not atoms. Using these results, we determine all hereditary classes defined by one or two forbidden induced subgraphs for which the property of not having simplicial vertices implies being an atom. For every other finitely defined hereditary graph class \(\mathcal{G}\) we give a polynomial-time algorithm for deciding if \(\mathcal{G}\) has this property. We have also performed the same research for the subgraph, minor and induced minor relations.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Atoms Versus Avoiding Simplicial Vertices

  • Karl Boddy,
  • Konrad K. Dabrowski,
  • Daniël Paulusma

摘要

A clique cut-set in a connected graph is a clique whose deletion results in a disconnected graph. A graph is an atom if it has no clique cut-set. There are many computational problems that are polynomial-time solvable on a hereditary graph class \(\mathcal {G}\) whenever they are polynomial-time solvable on the atoms in  \(\mathcal {G}\) . A simplicial vertex is one whose neighbourhood is a clique. If an atom is not a complete graph, then it cannot contain any simplicial vertices. Conversely, in many hereditary classes \(\mathcal {G}\) , we find that if a graph in \(\mathcal {G}\) does not contain any simplicial vertices, then it must be an atom. In this paper, we investigate the boundary between avoiding simplicial vertices and being an atom. We fully describe all minimal graphs without simplicial vertices that are not atoms. Using these results, we determine all hereditary classes defined by one or two forbidden induced subgraphs for which the property of not having simplicial vertices implies being an atom. For every other finitely defined hereditary graph class \(\mathcal{G}\) we give a polynomial-time algorithm for deciding if \(\mathcal{G}\) has this property. We have also performed the same research for the subgraph, minor and induced minor relations.