Isolation of k-cliques

DOI10.1016/J.DISC.2020.111879MaRDI QIDQ2182198zbMATH OpenOpenAlexFDO

Authors Peter Borg, Kurt Fenech, P. Kaemawichanurat

Publication date 21 May 2020

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1812.11098

zbMATH Keywords

dominating setcliqueclosed neighbourhoodisolating set

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

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)leqfracnk+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.

Recommendations

• Isolation of \(k\)-cliques. II
• Inequalities between the \(K_k\)-isolation number and the independent \(K_k\)-isolation number of a graph
• Isolation of cycles
• Bounds on a generalized domination parameter
• \( K_{1 , 2}\)-isolation in graphs

Cites work

• scientific article; zbMATH DE number 3172309 (Why is no real title available?)
• scientific article; zbMATH DE number 3596896 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• A survey of selected recent results on total domination in graphs
• Bibliography on domination in graphs and some basic definitions of domination parameters
• Distance \(k\)-domination, distance \(k\)-guarding, and distance \(k\)-vertex cover of maximal outerplanar graphs
• Distance domination, guarding and covering of maximal outerplanar graphs
• Independent domination in graphs: A survey and recent results
• Introduction to ``Topics on Domination
• Paired domination in graphs: a survey and recent results
• Partial domination -- the isolation number of a graph
• Total domination in graphs
• Towards a theory of domination in graphs
• \(k\)-domination and \(k\)-independence in graphs: A survey

Cited in

(30)

• \(K_{1, 2}\)-isolation number of claw-free cubic graphs
• Cycle isolation of graphs with small girth
• A note on the cycle isolation number of graphs
• Extremal graphs for the \(K_{1,2}\)-isolation number of graphs
• Graphs \(G\) where \(G-N[v]\) is a regular graph for each vertex \(v\)
• Graphs \(G\) where \(G-N[v]\) is a tree for each vertex \(v\)
• Disjoint isolating sets and graphs with maximum isolation number
• Isolation of regular graphs and \(k\)-chromatic graphs
• Isolation of connected graphs
• Algorithms – ESA 2005
• \( P_5\)-isolation in graphs
• Inequalities between the \(K_k\)-isolation number and the independent \(K_k\)-isolation number of a graph
• Algorithmic aspects of \(\{P_k\}\)-isolation in graphs and extremal graphs for a \(\{P_3\}\)-isolation bound
• Isolation of the diamond graph
• Isolation of squares in graphs
• Graphs \(G\) in which \(G-N[v]\) has a prescribed property for each vertex \(v\)
• \(k\)-isolation in graphs
• On the cycle isolation number of triangle-free graphs
• Graphs in which \(G - N[v]\) is a cycle for each vertex \(v\)
• Extensions of the Art Gallery Theorem
• Partial domination and irredundance numbers in graphs
• Isolation of cycles
• \( K_{1 , 2}\)-isolation in graphs
• Partial domination of hypergraphs
• Graphs with isolation number equal to one third of the order
• A sharp upper bound on the cycle isolation number of graphs
• Admissible property of graphs in terms of radius
• A note on the \(P_3\)-isolation number of a graph
• Admissible property of graphs in terms of independence number
• Isolation of \(k\)-cliques. II

This page was built for publication: Isolation of \(k\)-cliques

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2182198)