pith. sign in

arxiv: 1812.11098 · v1 · pith:KGK5FR5Mnew · submitted 2018-12-28 · 🧮 math.CO · cs.DM

Isolation of k-cliques

classification 🧮 math.CO cs.DM
keywords iotaresultcarocasecliquegraphhansbergbound
0
0 comments X
read the original abstract

For any positive integer $k$ and any $n$-vertex graph $G$, let $\iota(G,k)$ denote the size of a smallest set $D$ of vertices of $G$ such that the graph obtained from $G$ by deleting the closed neighbourhood of $D$ contains no $k$-clique. Thus, $\iota(G,1)$ is the domination number of $G$. We prove that if $G$ is connected, then $\iota(G,k) \leq \frac{n}{k+1}$ unless $G$ is a $k$-clique or $k = 2$ and $G$ is a $5$-cycle. The bound is sharp. The case $k=1$ is a classical result of Ore, and the case $k=2$ is a recent result of Caro and Hansberg. Our result solves a problem of Caro and Hansberg.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.