Proof of a conjecture on isolation of graphs with a universal vertex
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$. Settling a conjecture of Zhang and Wu, the first author proved 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 \frac{m+1}{k+2} $ unless $G$ is an $F$-copy or $F$ is a $3$-path and $G$ is a $6$-cycle. We prove another conjecture of Zhang and Wu by determining the graphs that attain the bound.
Authors
- Alastair Farrugia
- Peter Borg (ORCID: https://orcid.org/0000-0002-9668-3453)
Publication Details
- Journal
- Discrete Applied Mathematics
- Published
- 2026-09-07
- DOI
- https://doi.org/10.1016/j.dam.2026.08.016
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00