Borg, Peter; Fenech, Kurt; Kaemawichanurat, Pawaton Isolation of \(k\)-cliques. (English) Zbl 1440.05157 Discrete Math. 343, No. 7, Article ID 111879, 4 p. (2020). Summary: 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 [Theory of graphs. Providence, RI: American Mathematical Society (AMS) (1962; Zbl 0105.35401)], and the case \(k = 2\) is a recent result of Y. Caro and A. Hansberg [“Partial domination – the isolation number of a graph”, Filomat 31, No. 12, 3925–3944 (2017)]. Our result settles a problem of Caro and Hansberg [loc. cit.]. Cited in 1 ReviewCited in 13 Documents MSC: 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) Keywords:dominating set; isolating set; closed neighbourhood; clique Citations:Zbl 0105.35401 PDFBibTeX XMLCite \textit{P. Borg} et al., Discrete Math. 343, No. 7, Article ID 111879, 4 p. (2020; Zbl 1440.05157) Full Text: DOI arXiv References: [1] Alvarado, J.; Dantas, S.; Rautenbach, D., Distance \(k\)-domination, distance \(k\)-guarding, and distance \(k\)-vertex cover of maximal outerplanar graphs, Discrete Appl. Math., 194, 154-159 (2015) · Zbl 1319.05097 [2] Canales, S.; Hernández, G.; Martins, M.; Matos, I., Distance domination, guarding and covering of maximal outerplanar graphs, Discrete Appl. Math., 181, 41-49 (2015) · Zbl 1304.05022 [3] Caro, Y.; Hansberg, A., Partial domination - the isolation number of a graph, Filomat, 31, 12, 3925-3944 (2017) · Zbl 1488.05367 [4] Chellali, M.; Favaron, O.; Hansberg, A.; Volkmann, L., \(k\)-domination and \(k\)-independence in graphs: A survey, Graphs Combin., 28, 1-55 (2012) · Zbl 1234.05174 [5] Cockayne, E. J., (Domination of Undirected Graphs - A Survey. Domination of Undirected Graphs - A Survey, Lecture Notes in Mathematics, vol. 642 (1978), Springer), 141-147 · Zbl 0384.05052 [6] Cockayne, E. J.; Hedetniemi, S. T., Towards a theory of domination in graphs, Networks, 7, 247-261 (1977) · Zbl 0384.05051 [7] Desormeaux, W. J.; Henning, M. A., Paired domination in graphs: a survey and recent results, Util. Math., 94, 101-166 (2014) · Zbl 1300.05216 [8] Goddard, W.; Henning, M. A., Independent domination in graphs: A survey and recent results, Discrete Math., 313, 839-854 (2013) · Zbl 1260.05113 [9] Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Fundamentals of Domination in Graphs (1998), Marcel Dekker, Inc.: Marcel Dekker, Inc. New York · Zbl 0890.05002 [10] (Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Domination in Graphs: Advanced Topics (1998), Marcel Dekker, Inc.: Marcel Dekker, Inc. New York) · Zbl 0883.00011 [11] (Hedetniemi, S. T.; Laskar, R. C., Topics on Domination. Topics on Domination, Discrete Math., vol. 86 (1990)) · Zbl 0728.05056 [12] Hedetniemi, S. T.; Laskar, R. C., Bibliography on domination in graphs and some basic definitions of domination parameters, Discrete Math., 86, 257-277 (1990) · Zbl 0733.05076 [13] Henning, M. A., A survey of selected recent results on total domination in graphs, Discrete Math., 309, 32-63 (2009) · Zbl 1219.05121 [14] Henning, M. A.; Yeo, A., (Total Domination in Graphs. Total Domination in Graphs, Springer Monographs in Mathematics (2013), Springer: Springer New York) · Zbl 1408.05002 [15] Ore, O., (Theory of Graphs. Theory of Graphs, American Mathematical Society Colloquium Publications, vol. 38 (1962), American Mathematical Society: American Mathematical Society Providence, RI) · Zbl 0105.35401 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.