2024/07/25 by Peter Borg, Borg, Peter · 4 citations
Computer Science · Mathematics · #05C35 #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2407.18126
openalex publication_date 2024/07/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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,K1) is the domination number γ(G) of G, and ι(G,K2) 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) ≤ \lfloor (m+1)/(k+2) \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 ≥ 0 unless 1 ≤ m = k ≤ 2. New ideas, including deletion methods and divisibility considerations, are introduced in the proof of the conjecture.