Scholarlink

Let H(V, E) be a k-regular connected hypergraph with rank R on n vertices and m edges. A set of vertices \(S\subseteq V\) is an independent set if every two vertices in S are not adjacent. The independent number is the maximum cardinality of an independent set, denoted by \(\alpha (H)\) . In this paper, we prove the following inequality: \(\alpha (H)\ge \frac{m-(k-2)n-1}{R}\) , and the equality holds if and only if H is a hypertree with R-perfect matching. Based on the proofs, some combinatorial algorithms on the independent number are designed.

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

Some Combinatorial Algorithms on the Independent Number of k-Regular Connected Hypergraphs

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Zhuo Diao,
  • Haoyang Zou

摘要

Let H(V, E) be a k-regular connected hypergraph with rank R on n vertices and m edges. A set of vertices \(S\subseteq V\) is an independent set if every two vertices in S are not adjacent. The independent number is the maximum cardinality of an independent set, denoted by \(\alpha (H)\) . In this paper, we prove the following inequality: \(\alpha (H)\ge \frac{m-(k-2)n-1}{R}\) , and the equality holds if and only if H is a hypertree with R-perfect matching. Based on the proofs, some combinatorial algorithms on the independent number are designed.