Browsing by Author "Juan, ST"

Now showing 1 - 4 of 4

Group testing in bipartite graphs
(2002-03-01)
Juan, ST
;
Chang, GJ
;
應用數學系
;
Department of Applied Mathematics
This paper investigates the group testing problem in graphs as follows. Given a graph G = (V, E), determine the minimum number t(G) such that t(G) tests are sufficient to identify an unknown edge e with each test specifies a subset X subset of or equal to V and answers whether the unknown edge e is in G[X] or not. Damaschke proved that [log(2) e(G)] less than or equal to t(G) less than or equal to [log(2) e(G)] + 1 for any graph G, where e(G) is the number of edges of G. While there are infinitely many complete graphs that attain the upper bound, it was conjectured by Chang and Hwang that the lower bound is attained by all bipartite graphs. This paper verifies the conjecture for bipartite graphs G with e(G) less than or equal to 2(4) or 2(k-1) < e(G) less than or equal to 2(k-1) + 2(k-3) + 2(k-6) + 19(.)2(k-7/2) -1 for k greater than or equal to 5.
No-hole 2-distant colorings for unit interval graphs
(2001-10-01)
Chang, GJ
;
Juan, ST
;
Liu, DDF
;
應用數學系
;
Department of Applied Mathematics
Given a graph, a no-hole 2-distant coloring (also called N-coloring) is a function f that assigns to each vertex a non-negative integer (color) such that the separation of the colors of any pair of adjacent vertices must be at least 2, and all the colors used by f form a consecutive set (the no-hole assumption). The minimum consecutive N-span of G, csp(1)(G), is the minimum difference of the largest and the smallest colors used in an N-coloring of G, if there exists such a coloring; otherwise, define csp(1)(G) = infinity. Here we investigate the exact values of csp(1)(G) for unit interval graphs (also known as 1-unit sphere graphs). Earlier results by Roberts [18] indicate that if G is a unit interval graph on n vertices, then csp(1) (G) is either 2 chi (G) - 1 or 2 chi (G) - 2, if n > 2 chi (G) - 1; csp(1)(G) = infinity, if n < 2(G) - 1, where chi (G) denotes the chromatic number. We show that in the former case (when n > 2 chi (G) - 1), both values of csp(1)(G) are attained, and give several families of unit interval graphs such that csp(1)(G) = 2 chi (G) - 2. In addition, the exact values of csp(1)(G) are completely determined for unit interval graphs with chi (G) = 3.
T-colorings and T-edge spans of graphs
(1999-01-01)
Hu, SJ
;
Juan, ST
;
Chang, GJ
;
應用數學系
;
Department of Applied Mathematics
Suppose G is a graph and T is a set of non-negative integers that contains 0. A T-coloring of G is an assignment of a non-negative integer f(x) to each vertex x of G such that f(x) - f(y) is not an element of T whenever xy is an element of E(G). The edge span of a T-coloring f is the maximum value of f(x) - f(y) over all edges xy, and the T-edge span of a graph G is the minimum value of the edge span of a T-coloring of G. This paper studies the T-edge span of the dth power C-n(d) of the n-cycle C-n for T = {0, 1, 2, ..., k - 1}. In particular, we find the exact value of the T-edge span of C-n(d) for n = 0 or 1 (mod d + 1), and lower and upper bounds for other cases.
T-colorings and T-edge spans of graphs
(1999-01-01)
Hu, SJ
;
Juan, ST
;
Chang, GJ
;
應用數學系
;
Department of Applied Mathematics
Suppose G is a graph and T is a set of non-negative integers that contains 0. A T-coloring of G is an assignment of a non-negative integer f(x) to each vertex x of G such that \f(x) - f(y)\ is not an element of T whenever xy is an element of E(G). The edge span of a T-coloring f is the maximum value of \f(x) - f(y)\ over all edges xy, and the T-edge span of a graph G is the minimum value of the edge span of a T-coloring of G. This paper studies the T-edge span of the dth power C-n(d) of the n-cycle C-n for T = {0, 1, 2, ..., k - 1}. In particular, we find the exact value of the T-edge span of C-n(d) for n = 0 or 1 (mod d + 1), and lower and upper bounds for other cases.