標題: On the decycling number of generalized Kautz digraphs 作者: Lien, Min-YunKuo, JyhminFu, Hung-Lin應用數學系Department of Applied Mathematics 關鍵字: Generalized Kautz digraph;Interconnection networks;Feedback vertex number;Decycling number 公開日期: 1-Feb-2015 摘要: 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. URI: http://dx.doi.org/10.1016/j.ipl.2014.09.013http://hdl.handle.net/11536/124029 ISSN: 0020-0190 DOI: 10.1016/j.ipl.2014.09.013 期刊: INFORMATION PROCESSING LETTERS Volume: 115 起始頁: 209 結束頁: 211 Appears in Collections: Articles