Skip to main content
edited tags
Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187
Source Link

Maximum size of vertex set with no induced connected component on more than k vertices

An independent set of a graph is a collection of vertices such that the induced subgraph consists of disconnected vertices. The maximum possible cardinality of an independent set is then called the independence number of the graph.

For $k$ a positive integer, we define a $k$-independent set of a graph to be a collection of vertices such that the induced subgraph consists of components with $k$ vertices or fewer. (In particular, a $1$-independent set is the same as an independent set.) We then define the $k$-independence number of a graph to be the maximum possible cardinality of a $k$-independent set.

Have these notions of $k$-independent sets and $k$-independence numbers been studied before? If so, what names do they go by in the literature?

(Note: the term "$k$-independence number" does appear in the literature, but it asks for the induced subgraphs to have maximum degree at most $k$, rather than at most $k$ vertices.)