On the decycling number of generalized Kautz digraphs

Abstract

For n > d >= 2, the generalized Kautz digraph G(K)(d, n) is defined by congruence equations as follows: V(G(K)(d, n)) = {0, 1, 2, . . . , n - 1} and A (G(K)( (d, n)) = {(x, y)vertical bar y equivalent to -dx - i (mod n), 1 <= i <= d}. A set of vertices of a graph whose removal leaves an acyclic graph is called a decycling set of the graph. The minimum size of a decycling set of a graph G is referred to as the decycling number of G. Let f(d, n) be the decycling number of the generalized Kautz digraph G(K)(d, n). In this paper, we study f (d, n) for all n >= d >= 2. As a consequence, we obtain the upper bound of f(d, n) as follows: f(d, n) <= (1/2 - d-1/2d(2))n + d/2(d - t + 5) - 2, where n equivalent to t (mod(d + 1)). (C) 2014 Elsevier B.V. All rights reserved.