Isolation of connected graphs

DOI10.1016/J.DAM.2023.05.004MaRDI QIDQ6064845zbMATH OpenOpenAlexFDO

Authors Peter Borg

Publication date 11 December 2023

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

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

zbMATH Keywords

closed neighbourhoodconnected graphdominationisolation

Mathematics Subject Classification ID

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

Abstract: For a connected $n$-vertex graph $G$ and a set $mathcalF$ of graphs, let $iota(G,mathcalF)$ 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 graph in $mathcalF$. Let $mathcal{E}_k$ denote the set of connected graphs that have at least $k$ edges. By a result of Caro and Hansberg, $iota(G,mathcal{E}_1)leqn/3$ if $neq2$ and $G$ is not a $5$-cycle. The author recently showed that if $G$ is not a triangle and $mathcalC$ is the set of cycles, then $iota(G,mathcalC)leqn/4$. We improve this result by showing that $iota(G,mathcal{E}_3)leqn/4$ if $G$ is neither a triangle nor a $7$-cycle. Let $r$ be the number of vertices of $G$ that have only one neighbour. We determine a set $mathcalS$ of six graphs such that $iota(G,mathcal{E}_2)leq(4n-r)/14$ if $G$ is not a copy of a member of $mathcalS$. The bounds are sharp.

Recommendations

• Isolation of cycles
• \( K_{1 , 2}\)-isolation in graphs
• A sharp upper bound on the cycle isolation number of graphs
• \(k\)-isolation in graphs

Cites work

• \( K_{1 , 2}\)-isolation in graphs
• Admissible property of graphs in terms of radius
• Bibliography on domination in graphs and some basic definitions of domination parameters
• Extensions of the Art Gallery Theorem
• 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?)
• Inequalities between the \(K_k\)-isolation number and the independent \(K_k\)-isolation number of a graph
• Introduction to ``Topics on Domination
• Isolation number of maximal outerplanar graphs
• Isolation of \(k\)-cliques
• Isolation of \(k\)-cliques. II
• Isolation of cycles
• Isolation of the diamond graph
• Partial domination -- the isolation number of a graph
• Partial domination of maximal outerplanar graphs
• Towards a theory of domination in graphs

Cited in

(18)

• Neighbor Isolated Tenacity of Graphs
• A sharp upper bound on the cycle isolation number of graphs
• Algorithmic aspects of \(\{P_k\}\)-isolation in graphs and extremal graphs for a \(\{P_3\}\)-isolation bound
• Isolation of squares in graphs
• On the cycle isolation number of triangle-free graphs
• A note on the \(P_3\)-isolation number of a graph
• Solution to a 3-path isolation problem for subcubic graphs
• New results on the 1-isolation number of graphs without short cycles
• The probabilistic upper bounds on the isolation number of a graph
• Total isolation of k-cliques in a graph
• Isolation of connected graphs in terms of size
• A characterization of graphs with maximum k-clique isolation number
• Proof of a conjecture on isolation of graphs dominated by a vertex
• A characterization of graphs with maximum cycle isolation number
• Green's theorem and isolation in planar graphs
• Proof of a conjecture on isolation of cycles in graphs
• Upper bounds on the k-isolation number
• Solution to a problem on isolation of 3-vertex paths

This page was built for publication: Isolation of connected graphs

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