A probabilistic algorithm for bounding the total restrained domination number of a K1,ℓ-free graph

Let G = (V, V , E ) be a graph. A set S C V is a total restrained dominating set if every vertex is adjacent to a vertex in S , and every vertex in V - S is adjacent to a vertex in V - S . The total restrained domination number of G , denoted gamma t r ( G ), is the smallest cardinality of a total restrained dominating set of G . In this paper we show that if G is a K 1 ,& ell;-free graph with delta >= & ell; >= 3 and delta >= 5, then ( ) 1- - (2 delta delta - 3) gamma tr ( G ) <= n + o delta (1) . (2 delta ) delta delta - 1 (c) 2024 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.