2020/01/27 by Odile Favaron, Favaron, Odile, Pawaton Kaemawichanurat +1
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2001.09633
openalex publication_date 2020/01/27 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
For a graph G, a vertex subset S \⊆ V(G) is said to be\nKk-isolating if G - NG[S] does not contain Kk as a subgraph. The\nKk-isolation number of G, denoted by \ιk(G), is the minimum\ncardinality of a Kk-isolating set of G. Analogously, S is said to be\nindependent Kk-isolating if S is a Kk-isolating set of G and\nG[S] has no edge. The independent Kk-isolation number of G, denoted by\n\ι'k(G), is the minimum cardinality of an independent Kk-isolating\nset of G. Clearly, when k = 1, we have \γ(G) = \ι1(G) and i(G)\n= \ι'1(G) where \γ(G) and i(G) are the domination and\nindependent domination numbers. For classic results between \γ(G) and\ni(G), in 1978, Allan and Laskar proved that \γ(G) = i(G) for all K1,\n3-free graphs and this result was generalized to K1, r-free graphs by\nBollob acuteas and Cockayne in 1979. In 2013, Rad and Volkmann proved that\nthe ratio i(G)/\γ(G) is at most \Δ(G)/2 when \Δ(G) \∈ 3, 4,\n5 . Further, Furuya et. al. proved that when \Δ(G) \≥ 6, we have\ni(G)/\γ(G) \≤ \Δ(G) - 2\√(\Δ(G)) + 2. In this paper, for a\nsmallest Kk-isolating set S, we prove that \ι'k(G)\≤\n-\(\ιk2(G))/(\ℓ) +ik(G)(\Δ +2)-\ℓ \Δ where \ℓ is the\nnumber of some specific vertices of S such that the union of their closed\nneighborhoods in S is S. We prove that this bound is sharp. A special case\nof our main theorem implies \ι'k(G)/\ιk(G) \≤ \Δ(G) -\n2\√(\Δ(G)) + 2. Further, we find an inequality between \ι'k(G)\nand \ιk(G) when G is K1, r-free graph. This also generalizes the\nresult of Bollob acuteas and Cockayne.\n