A generalization of the independence number

Katona, Gyula (2022) A generalization of the independence number. DISCRETE APPLIED MATHEMATICS, 321. pp. 1-3. ISSN 0166-218X

Preview

Text 1-s2.0-S0166218X22002116-main.pdf - Published Version Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (319kB) | Preview

Abstract

Jianguo Qian, Konrad Engel and Wei Xu (Dass et al., 2015) gave a generalization of Sperner's theorem (Sperner, 1928): n and m are given integers, they found the minimum number of pairs Yi⊆Yj(i≠j) in a multifamily {Y1,…,Ym} of not necessarily different subsets of an n-element set. Here a far reaching generalization and easier proof is given. Let G be a graph and m an integer, choose m vertices with possible repetitions in such a way that the number of adjacent pairs (including the repeated vertices) is minimum. It is proved that the following choice gives the minimum: take the vertices of a largest independent set in G with nearly equal multiplicities. © 2022 The Author(s)

Actions (login required)

Edit Item