標題: On the decycling number of generalized Kautz digraphs
作者: Lien, Min-Yun
Kuo, Jyhmin
Fu, Hung-Lin
應用數學系
Department of Applied Mathematics
關鍵字: Generalized Kautz digraph;Interconnection networks;Feedback vertex number;Decycling number
公開日期: 1-二月-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.013
http://hdl.handle.net/11536/124029
ISSN: 0020-0190
DOI: 10.1016/j.ipl.2014.09.013
期刊: INFORMATION PROCESSING LETTERS
Volume: 115
起始頁: 209
結束頁: 211
顯示於類別:期刊論文