# Proof of a conjecture on isolation of graphs dominated by a vertex

Preprint · Peter Borg

- Archive id: arxiv:2407.18126
- Published: 2024-07-25
- Venue: Discrete Applied Mathematics 371 (2025), 247-253
- DOI: https://doi.org/10.1016/j.dam.2025.04.009
- arXiv: https://arxiv.org/abs/2407.18126
- Source URL: https://arxiv.org/abs/2407.18126
- PDF: https://arxiv.org/pdf/2407.18126
- Provenance: arxiv

## Abstract

A copy of a graph $F$ is called an $F$-copy. For any graph $G$, the $F$-isolation number of $G$, denoted by $ι(G,F)$, is the size of a smallest subset $D$ of the vertex set of $G$ such that the closed neighbourhood $N\[D\]$ of $D$ in $G$ intersects the vertex sets of the $F$-copies contained by $G$ (equivalently, $G-N\[D\]$ contains no $F$-copy). Thus, $ι(G,K\_1)$ is the domination number $γ(G)$ of $G$, and $ι(G,K\_2)$ is the vertex-edge domination number of $G$. We prove that if $F$ is a $k$-edge graph, $γ(F) = 1$ (that is, $F$ has a vertex that is adjacent to all the other vertices of $F$), and $G$ is a connected $m$-edge graph, then $ι(G,F) \\leq \\big\\lfloor \\frac{m+1}{k+2} \\big\\rfloor$ unless $G$ is an $F$-copy or $F$ is a $3$-path and $G$ is a $6$-cycle. This was recently posed as a conjecture by Zhang and Wu, who settled the extreme case where $F$ is a star. The result for the other extreme case where $F$ is a clique had been obtained by Fenech, Kaemawichanurat and the present author. The bound is attainable for any $m \\geq 0$ unless $1 \\leq m = k \\leq 2$. New ideas, including deletion methods and divisibility considerations, are introduced in the proof of the conjecture.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.