Maximizing the number of independent sets of fixed size in KnK_n-covered graphs

preprint2020arXivOpen access

Abstract

A graph GG is HH-covered by some given graph HH if each vertex in GG is contained in a copy of HH. In this note, we give the maximum number of independent sets of size t≥3t\ge 3 in KnK_n-covered graphs of size N≥n+t−1N\ge n+t-1 and determine its extremal graph. The result answers a question proposed by Chakraborit and Loh. The proof uses an edge-switching operation of hypergraphs which remains the number of independent sets nondecreasing.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.