Partial domination - the isolation number of a graph

2015/04/30 by Caro, Yair, Hansberg, Adriana · 8 citations
#05C65 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1504.08055

Abstract

We prove the following result: If G be a connected graph on n ≥ 6 vertices, then there exists a set of vertices D with |D| ≤ (n)/(3) and such that V(G) ∖ N[D] is an independent set, where N[D] is the closed neighborhood of D. Furthermore, the bound is sharp. This seems to be the first result in the direction of partial domination with constrained structure on the graph induced by the non-dominated vertices, which we further elaborate in this paper.

Cited by

• Isolation of non-triangle cycles in graphs
• All-k-Isolation in Trees
• Isolation number: Cartesian and lexicographic products and generalized Sierpiński graphs
• On the isolation number of graphs with minimum degree four
• Upper bounds on the k-isolation number
• Bounds on the game isolation number and exact values for paths and cycles
• Proof of a conjecture on isolation of graphs with a universal vertex
• Solution to a problem on isolation of 3-vertex paths

Related

• Inequalities between Partial Domination and Independent Partial\n Domination in Graphs
• Partial domination of middle graphs
• On independent domination of regular graphs
• Partial Domination and Irredundance Numbers in Graphs
• Partial Domination in Graphs