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

The number of maximal dissociation sets in unicyclic graphs

  • Long Jin,
  • Jianxi Li,
  • Wai Chee Shiu

摘要

A vertex subset \(S \subseteq V(G)\) S V ( G ) is called a dissociation set of a graph G if \(\Delta (G[S])\le 1\) Δ ( G [ S ] ) 1 . A dissociation set S of G is maximal if it is not a proper subset of any other dissociation set of G. Let \(\phi (G)\) ϕ ( G ) be the number of maximal dissociation sets in G. Zhang, Qian, and Huang (2024) proved that for any tree T of order n, , and characterized all trees T with . In this paper, we further study the number of maximal dissociation sets for unicyclic graphs, and prove that for any unicyclic graph U of order n, \(\phi (U)\ge \left\lfloor \frac{n}{2}\right\rfloor +2\) ϕ ( U ) n 2 + 2 . Moreover, all unicyclic graphs U with \(\phi (U)= \left\lfloor \frac{n}{2}\right\rfloor +2\) ϕ ( U ) = n 2 + 2 are completely characterized.