Browsing by Author "Zhu, XD"

Now showing 1 - 5 of 5

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 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.
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.
Equivalence of the 1-rate model to the classical model on strictly nonblocking switching networks
(2004)
Chen, WR
;
Hwang, FK
;
Zhu, XD
;
應用數學系
;
Department of Applied Mathematics
In the 1-rate(f) network, each link can carry up to f messages for some integer f. The classical model is the special case when f = 1. We show that a network is strictly nonblocking under the 1-rate(f) model if and only if it is strictly nonblocking under the classical model.
Pseudo-Hamiltonian-connected graphs
(2000-03-30)
Chang, GJ
;
Zhu, XD
;
應用數學系
;
Department of Applied Mathematics
Given a graph G and a positive integer k, denote by G[k] the graph obtained from G by replacing each vertex of G with an independent set of size k. A graph G is called pseudo-k Hamiltonian-connected if G[k] is Hamiltonian-connected, i.e., every two distinct vertices of G[k] are connected by a Hamiltonian path. A graph G is called pseudo Hamiltonian-connected if it is pseudo-k Hamiltonian-connected for some positive integer k. This paper proves that a graph G is pseudo-Hamiltonian-connected if and only if for every non-empty proper subset X of V(G), N(X) > X. The proof of the characterization also provides a polynomial-time algorithm that decides whether or not a given graph is pseudo-Hamiltonian-connected. The characterization of pseudo-Hamiltonian-connected graphs also answers a question of Richard Nowakowski, which motivated this paper. (C) 2000 Elsevier Science B.V. All rights reserved.