Browsing by Author "Lien, Min-Yun"

Now showing 1 - 2 of 2

On the decycling number of generalized Kautz digraphs
(2015-02-01)
Lien, Min-Yun
;
Kuo, Jyhmin
;
Fu, Hung-Lin
;
應用數學系
;
Department of Applied Mathematics
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.
The decycling number of outerplanar graphs
(2013-05-01)
Chang, Huilan
;
Fu, Hung-Lin
;
Lien, Min-Yun
;
應用數學系
;
Department of Applied Mathematics
For a graph G, let tau(G) be the decycling number of G and c(G) be the number of vertex-disjoint cycles of G. It has been proved that c(G)a parts per thousand currency sign tau(G)a parts per thousand currency sign2c(G) for an outerplanar graph G. An outerplanar graph G is called lower-extremal if tau(G)=c(G) and upper-extremal if tau(G)=2c(G). In this paper, we provide a necessary and sufficient condition for an outerplanar graph being upper-extremal. On the other hand, we find a class of outerplanar graphs none of which is lower-extremal and show that if G has no subdivision of S for all , then G is lower-extremal.