Isolation of k-cliques

DOI10.1016/J.DISC.2020.111879zbMATH Open1440.05157arXiv1812.11098OpenAlexW3010685994MaRDI QIDQ2182198FDOQ2182198

Authors: Peter Borg, Kurt Fenech, P. Kaemawichanurat 

Publication date: 21 May 2020

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

dominating setcliqueclosed neighbourhoodisolating set

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Total domination in graphs
• \(k\)-domination and \(k\)-independence in graphs: A survey
• A survey of selected recent results on total domination in graphs
• Bibliography on domination in graphs and some basic definitions of domination parameters
• Independent domination in graphs: A survey and recent results
• Title not available (Why is that?)
• Towards a theory of domination in graphs
• Introduction to ``Topics on Domination
• Distance domination, guarding and covering of maximal outerplanar graphs
• Distance \(k\)-domination, distance \(k\)-guarding, and distance \(k\)-vertex cover of maximal outerplanar graphs
• Paired domination in graphs: a survey and recent results
• Title not available (Why is that?)
• Partial domination -- the isolation number of a graph

Cited In (30)

• 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 squares in graphs
• Isolation of the diamond graph
• \(k\)-isolation in graphs
• On the cycle isolation number of triangle-free graphs
• Partial domination and irredundance numbers in graphs
• Graphs \(G\) in which \(G-N[v]\) has a prescribed property for each vertex \(v\)
• Graphs in which \(G - N[v]\) is a cycle for each vertex \(v\)
• Extensions of the Art Gallery Theorem
• Isolation of cycles
• Partial domination of hypergraphs
• \( K_{1 , 2}\)-isolation in graphs
• 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
• \(K_{1, 2}\)-isolation number of claw-free cubic graphs
• Cycle isolation of graphs with small girth

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)