2022/06/14 by Pawaton Kaemawichanurat, Kaemawichanurat, Pawaton, Odile Favaron +1
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2206.07208
openalex publication_date 2022/06/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A dominating set of a graph G=(V,E) is a vertex set D such that every vertex in V(G) ∖ D is adjacent to a vertex in D. The cardinality of a smallest dominating set of D is called the domination number of G and is denoted by γ(G). A vertex set D is a k-isolating set of G if G - NG[D] contains no k-cliques. The minimum cardinality of a k-isolating set of G is called the k-isolation number of G and is denoted by ιk(G). Clearly, γ(G) = ι1(G). A vertex set I is irredundant if, for every non-isolated vertex v of G[I], there exists a vertex u in V ∖ I such that NG(u) ∩ I = \v\. An irredundant set I is maximal if the set I ∪ \u\ is no longer irredundant for any u ∈ V(G) ∖ I. The minimum cardinality of a maximal irredundant set is called the irredundance number of G and is denoted by ir(G). Allan and Laskar \citeAL1978 and Bollobás and Cockayne \citeBoCo1979 independently proved that γ(G) < 2ir(G), which can be written ι1(G) < 2ir(G), for any graph G. In this paper, for a graph G with maximum degree Δ, we establish sharp upper bounds on ιk(G) in terms of ir(G) for Δ- 2 ≤ k ≤ Δ+ 1.