标题: | 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 |
显示于类别: | Articles |