Browsing by Author "Chang, GJ"

Now showing 1 - 20 of 72

A finiteness theorem for maximal independent sets
(1996)
Jou, MJ
;
Chang, GJ
;
Lin, C
;
Ma, TH
;
應用數學系
Denote by mi(G) the number of maximal independent sets of G. This paper studies the set S(k) of all graphs G with mi(G) = k and without isolated vertices (except G congruent to K-1) or duplicated vertices. We determine S(1), S(2), and S(3) and prove that V(G) less than or equal to 2(k-1) + k - 2 for any G in S(k) and k greater than or equal to 2; consequently, S(k) is finite for any k.
A simple and direct derivation for the number of noncrossing partitions
(1998-06-01)
Liaw, SC
;
Yeh, HG
;
Hwang, FK
;
Chang, GJ
;
應用數學系
Kreweras considered the problem of counting noncrossing partitions of the set {1, 2, ..., n}, whose elements are arranged into a cycle in its natural order, into p parts of given sizes n(1), n(2), ..., n(p) (but not specifying which part gets which size). He gave a beautiful and surprising result whose proof resorts to a recurrence relation. In this paper we give a direct, entirely bijective, proof starting from the same initial idea as Kreweras' proof.
Algorithmic aspect of k-tuple domination in graphs
(2002-09-01)
Liao, CS
;
Chang, GJ
;
應用數學系
;
Department of Applied Mathematics
In a graph G, a vertex is said to dominate itself and all of its neighbors. For a fixed positive integer k, the k-tuple domination problem is to find a minimum sized vertex subset such that every vertex in the graph is dominated by at least k vertices in this set. The present paper studies the k-tuple domination problem in graphs from an algorithmic point of view. In particular, we give a linear-time algorithm for the 2-tuple domination problem in trees by employing a labeling method.
Algorithmic aspects of counting independent sets
(2002-10-01)
Jou, MJ
;
Chang, GJ
;
應用數學系
;
Department of Applied Mathematics
This paper studied the problems of counting independent sets, maximal independent sets, and maximum independent sets of a graph from an algorithmic point of view. In particular, we present linear-time algorithms for these problems in trees and unicyclic graphs.
Algorithmic aspects of linear k-arboricity
(1999-03-01)
Chang, GJ
;
應用數學系
;
Department of Applied Mathematics
For a fixed positive integer k, the linear k-arboricity la(k)(G) of a graph G is the minimum number l such that the edge set E(G) can be partitioned into l disjoint sets, each induces a subgraph whose components are paths of lengths at most k. This paper examines linear k-arboricity from an algorithmic point of view. In particular, we present a linear-time algorithm for determining whether a tree T has la(2)(T) less than or equal to m. We also give a characterization for a tree T with maximum degree 2m having la(2)(T) = m.
Algorithmic aspects of the generalized clique-transversal problem on chordal graphs
(1996-05-20)
Chang, MS
;
Chen, YH
;
Chang, GJ
;
Yan, JH
;
應用數學系
Suppose G=(V,E) is a graph in which each maximal clique C-i is associated with an integer r(i), where 0 less than or equal to r(i) less than or equal to\C-i\. The generalized clique transversal problem is to determine the minimum cardinality of a subset D of V such that \D boolean AND C-i\greater than or equal to r(i) for every maximal clique C-i of G. The problem includes the clique-transversal problem, the i,1 clique-cover problem, and for perfect graphs, the maximum q-colorable subgraph problems as special cases. This paper gives complexity results for the problem on subclasses of chordal graphs, e.g., strongly chordal graphs, k-trees, split graphs, and undirected path graphs.
Algorithmic aspects of the generalized clique-transversal problem on chordal graphs
(1996-05-20)
Chang, MS
;
Chen, YH
;
Chang, GJ
;
Yan, JH
;
應用數學系
Suppose G=(V,E) is a graph in which each maximal clique C-i is associated with an integer r(i), where 0 less than or equal to r(i) less than or equal toC-i. The generalized clique transversal problem is to determine the minimum cardinality of a subset D of V such that D boolean AND C-igreater than or equal to r(i) for every maximal clique C-i of G. The problem includes the clique-transversal problem, the i,1 clique-cover problem, and for perfect graphs, the maximum q-colorable subgraph problems as special cases. This paper gives complexity results for the problem on subclasses of chordal graphs, e.g., strongly chordal graphs, k-trees, split graphs, and undirected path graphs.
Bipartite Steinhaus graphs
(1999-09-01)
Lee, YS
;
Chang, GJ
;
應用數學系
;
Department of Applied Mathematics
A Steinhaus matrix is a symmetric 0-1 matrix [a(i,j)](nxn) such that a(i,i) = 0 for 0 less than or equal to i less than or equal to n - 1 and a(i,j) = (a(i-1,j-1) + a(i-1,j)) (mod 2) for 1 less than or equal to i < j less than or equal to n-1. A Steinhaus graph is a graph whose adjacency matrix is a Steinhaus matrix. In this paper, we present a new characterization of bipartite Steinhaus graphs.
Channel graphs of bit permutation networks
(2001-07-28)
Tong, LD
;
Wang, FK
;
Chang, GJ
;
應用數學系
;
Department of Applied Mathematics
Channel graphs have been widely used in the study of blocking networks. In this paper, we show that a bit pen-nutation network has a unique channel graph if and only if it is connected, and two connected bit pen-nutation networks are isomorphic if and only if their channel graphs are isomorphic. (C) 2001 Elsevier Science B.V. All rights reserved.
Characterizations of bipartite Steinhaus graphs
(1999-03-28)
Chang, GJ
;
DasGupta, B
;
Dymacek, WM
;
Furer, M
;
Koerlin, M
We characterize bipartite Steinhaus graphs in three ways by partitioning them into four classes and we describe the color sets for each of these classes. An interesting recursion had previously been given for the number of bipartite Steinhaus graphs and we give two fascinating closed forms for this recursion. Also, we exhibit a lower bound, which is achieved infinitely often, for the number of bipartite Steinhaus graphs. (C) 1999 Elsevier Science B.V. All rights reserved.
Characterizing bit permutation networks
(1998)
Chang, GJ
;
Hwang, FK
;
Tong, LD
;
應用數學系
;
Department of Applied Mathematics
In recent years, many multistage interconnection networks using 2 x 2 switching elements have been proposed for parallel architectures. Typical examples are baseline networks, banyan networks, shuffle-exchange networks and their inverses. As these networks are blocking, such networks with extra stages have also been studied extensively. These include Benes networks and Delta + Delta' networks. Recently, Hwang, Liaw and Yeh studied k-extra-stage networks which is a generalization of the above networks. They also investigated the equivalence issue among some of these networks. In this paper, we study a more general class of networks, which we call (m + 1)-stage d-nary bit permutation networks. We characterize the equivalence of such networks by sequence of positive integers.
Characterizing bit permutation networks
(1999-07-01)
Chang, GJ
;
Hwang, FK
;
Tong, LD
;
應用數學系
;
Department of Applied Mathematics
In recent years, many multistage interconnection networks using 2 x 2 switching elements have been proposed for parallel architectures. Typical examples are baseline networks, banyan networks, shuffle-exchange networks, and their inverses. As these networks are blocking, such networks with extra stages have also been studied extensively. These include Benes networks and Delta + Delta' networks. Recently, Hwang et al, studied k-extra-stage networks, which are a generalization of the above networks. They also investigated the equivalence issue among some of these networks. In this paper, we studied a more general class of networks, which we call (m + 1)-stage d-nary bit permutation networks. We characterize the equivalence of such networks by sequence of positive integers. (C) 1999 John Wiley & Sons, Inc.
Circular chromatic numbers and fractional chromatic numbers of distance graphs
(1998-05-01)
Chang, GJ
;
Huang, LL
;
Zhu, XD
;
應用數學系
;
Department of Applied Mathematics
This paper studies circular chromatic numbers and fractional chromatic numbers of distance graphs G(Z, D) for various distance sets D. In particular, we determine these numbers for those D sets of size two, for some special D sets of size three, for D = {1, 2,..., m, n} with 1 less than or equal to m < n, for D = {q, q + 1,..., p} with q less than or equal to p, and for D = {1, 2,..., m} - {k} with 1 less than or equal to k less than or equal to m. (C) 1998 Academic Press.
Circular chromatic numbers of distance graphs with distance sets missing multiples
(2000-02-01)
Huang, LL
;
Chang, GJ
;
應用數學系
;
Department of Applied Mathematics
Given positive integers m, k, s with m > sk, let D-m,D-k,D-s represent the set {1, 2,..., m} {k, 2k,..., sk}. The distance graph G(Z, D-m,D-k,D-s) has as vertex set all integers Z and edges connecting i and j whenever i - j is an element of D-m,D-k,D-s. This paper investigates chromatic numbers and circular chromatic numbers of the distance graphs G(Z, D-m,D-k,D-s). Deuber and Zhu [8] and Liu [13] have shown that [m+sk+1/s+1] less than or equal to chi(G(Z, D-m,D-k,D-s)) less than or equal to [m+sk+1/s+1] + 1 when m greater than or equal to (s + 1)k. In this paper, by establishing bounds for the circular chromatic number chi(C)(G(Z, D-m,D-k,D-s)) of G(Z, D-m,D-k,D-s), we determine the values of chi(G(Z, D-m,D-k,D-s)) for all positive integers m, k, s and chi(C)(G(Z, D-m,D-k,D-s)) for some positive integers m, k, s. (C) 2000 Academic Press.
Circular chromatic numbers of Mycielski's graphs
(1999-07-28)
Chang, GJ
;
Huang, LL
;
Zhu, XD
;
應用數學系
;
Department of Applied Mathematics
In a search for triangle-free graphs with arbitrarily large chromatic numbers, Mycielski developed a graph transformation that transforms a graph G into a new graph mu(G), we now call the Mycielskian of G, which has the same clique number as G and whose chromatic number equals chi(G) + 1. Let mu(n)(G) = mu(mu(n-1)(G)) for n greater than or equal to 2. This paper investigates the circular chromatic numbers of Mycielski's graphs. In particular, the following results are proved in this paper: (1) for any graph G of chromatic number n, chi(c)(mu(n-1)(G)) less than or equal to chi(mu(n-1)(G)) - 1/2; (2) if a graph G satisfies chi(c)(G) less than or equal to chi(G) - 1/d with d = 2 or 3, then chi(c)(mu(2)(G)) less than or equal to chi(mu(2)(G)) - 1/d; (3) for any graph G of chromatic number 3, chi(c)(mu(G)) = chi(mu(G)) = 4; (4) chi(c)(mu(K-n)) = chi(mu(K-n)) = n + 1 for n greater than or equal to 3 and chi(c)(mu(2)(K-n)) = chi(mu(2)(K-n)) = n + 2 for n greater than or equal to 4. (C) 1999 Elsevier Science B.V. All rights reserved.
Cordial labeling of mK(n)
(1997-05-15)
Kuo, D
;
Chang, GJ
;
Kwong, YHH
;
應用數學系
;
Department of Applied Mathematics
Suppose G = (V,E) is a graph with vertex set V and edge set E. A vertex labeling f: V --> (0, 1) induces an edge labeling f*: E --> (0, 1) defined by f*(ny) = If(x)- f(y)l. For i is an element of (0, 1), let v(f)(i) and e(f)(i) be the number of vertices v and edges e with f(v) = i and f*(e) = i, respectively. A graph G is cordial if there exists a vertex labeling f such that v(f)(0) - v(f)(1)less than or equal to 1 and e(f)(0) - e(f)(1) less than or equal to 1. This paper determines all m and n for which mK(n) is cordial.
Distance graphs and T-coloring
(1999-03-01)
Chang, GJ
;
Liu, DDF
;
Zhu, XD
;
應用數學系
;
Department of Applied Mathematics
We discuss relationships among T-colorings of graphs and chromatic numbers, fractional chromatic numbers, and circular chromatic numbers of distance graphs. We first prove that for any finite integral set T that contains 0, the asymptotic T-coloring ratio R(T) is equal to the fractional chromatic number of the distance graph G(Z, D), where D = T-{0}. This fact is then used to study the distance graphs with distance sets of the form D-m,D- k = {1, 2, ..., m}- {k}. The chromatic numbers and the fractional chromatic numbers of G(Z, D-m,D- k) are determined for all values of m and k. Furthermore, circular chromatic numbers of G(Z, D-m,D- k) fur some special values of m and k are obtained. (C) 1999 Academic Press.
Domination in distance-hereditary graphs
(2002-01-15)
Chang, MS
;
Wu, SC
;
Chang, GJ
;
Yeh, HG
;
應用數學系
The domination problem and its variants have been extensively studied in the literature. In this paper we investigate the domination problem in distance-hereditary graphs, In particular, we give a linear-time algorithm for the domination problem in distance-hereditary graphs by a labeling approach. We actually solve a more general problem, called the L-domination problem, which also includes the total domination problem as a special case. (C) 2002 Elsevier Science B.V. All rights reserved.
Enumerating consecutive and nested partitions for graphs
(1998-01-01)
Hwang, FK
;
Chang, GJ
;
應用數學系
;
Department of Applied Mathematics
Consecutive and nested partitions have been extensively studied in the set-partition problem as tools with which to search efficiently for an optimal partition. We extend the study of consecutive and nested partitions on a set of integers to the vertex-set of a graph. A subset of vertices is considered consecutive if the subgraph induced by the subset is connected. In this sense the partition problem on a set of integers can be treated as a special case when the graph is a line. In this paper we give the number of consecutive and nested partitions when the graph is a cycle. We also give a partial order on general graphs with respect to these numbers. (C) 1998 Academic Press Limited.
Enumerating consecutive and nested partitions for graphs
(1998-01-01)
Hwang, FK
;
Chang, GJ
;
應用數學系
;
Department of Applied Mathematics
Consecutive and nested partitions have been extensively studied in the set-partition problem as tools with which to search efficiently for an optimal partition. We extend the study of consecutive and nested partitions on a set of integers to the vertex-set of a graph. A subset of vertices is considered consecutive if the subgraph induced by the subset is connected. In this sense the partition problem on a set of integers can be treated as a special case when the graph is a line. In this paper we give the number of consecutive and nested partitions when the graph is a cycle. We also give a partial order on general graphs with respect to these numbers. (C) 1998 Academic Press Limited.