Browsing by Author "Kuo, D"

Now showing 1 - 6 of 6

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.
Integral sum numbers of graphs
(2000-01-01)
Liaw, SC
;
Kuo, D
;
Chang, GJ
;
應用數學系
;
Department of Applied Mathematics
The sum graph of a set S of positive integers is the graph G(+)(S) having S as its vertex set, with two distinct vertices adjacent whenever their sum is in S. If S is allowed to be a subset of all integers, a graph so obtained is called an integral sum graph. The integral sum number of a given graph G is the smallest number of isolated vertices which when added to G result in an integral sum graph. In this paper, we find the integral sum numbers of caterpillars, cycles, wheels, and complete bipartite graphs.
On L(d, 1)-labelings of graphs
(2000-06-06)
Chang, GJ
;
Ke, WT
;
Kuo, D
;
Liu, DDF
;
Yeh, RK
Given a graph G and a positive integer d, an L(d, 1)-labeling of G is a function f that assigns to each vertex of G a non-negative integer such that if two vertices u and u are adjacent, then f(u) - f(v) greater than or equal to d; if u and v are not adjacent but there is a two-edge path between them, then f(u)- f(v) greater than or equal to 1. The L(d, 1)-number of G, lambda(d)(G), is defined as the minimum m such that there is an L(d, 1)-labeling f of G with f(V) subset of or equal to {0, 1, 2,,.., m}. Motivated by the channel assignment problem introduced by Hale (Proc, IEEE 68 (1980) 1497-1514), the L(2, 1)-labeling and the L(1, 1)-labeling (as d = 2 and 1, respectively) have been studied extensively in the past decade. This article extends the study to all positive integers d. We prove that lambda(d)(G) less than or equal to Delta(2) + (d - 1)Delta for any graph G with maximum degree d. Different lower and upper bounds of lambda(d)(G) for some families of graphs including trees and chordal graphs are presented. In particular, we show that the lower and the upper bounds for trees are both attainable, and the upper bound for chordal graphs can be improved for several subclasses of chordal graphs. (C) 2000 Elsevier Science B,V. All rights reserved.
Signed degree sequences of signed graphs
(1997-10-01)
Yan, JH
;
Lih, KW
;
Kuo, D
;
Chang, GJ
;
應用數學系
This paper gives necessary and sufficient conditions for an integral sequence to be the signed degree sequence of a signed graph or a signed tree, answering a question raised by Chartrand et al. (1994). (G. Chartrand, H. Gavlas, F. Harary, and M. Schultz, On signed degrees in signed graphs, Czech. Math. J.44 (1994), 677-690). (C) 1997 John Wiley & Sons, Inc.
Signed degree sequences of signed graphs
(1997-10-01)
Yan, JH
;
Lih, KW
;
Kuo, D
;
Chang, GJ
;
應用數學系
This paper gives necessary and sufficient conditions for an integral sequence to be the signed degree sequence of a signed graph or a signed tree, answering a question raised by Chartrand et al. (1994). (G. Chartrand, H. Gavlas, F. Harary, and M. Schultz, On signed degrees in signed graphs, Czech. Math. J.44 (1994), 677-690). (C) 1997 John Wiley & Sons, Inc.
The L(2,1)-labeling problem on graphs
(1996-05-01)
Chang, GJ
;
Kuo, D
;
交大名義發表
;
應用數學系
;
National Chiao Tung University
An L(2, 1)-labeling of a graph G is a function f from the vertex set V(G) to the set of all nonnegative integers such that f(x) - f(y) greater than or equal to 2 if d(x, y) = 1 and f(x) - f(y) greater than or equal to 1 if d(x, y) = 2. The L(2, 1)-labeling number lambda(G) of G is the smallest number Ic such that G has an L(2, 1)-labeling with max{f(v) : v is an element of V(G)} = k. In this paper, we give exact formulas of lambda(G boolean OR H) and lambda(G + H). We also prove that lambda(G) less than or equal to Delta(2) + Delta for any graph G of maximum degree Delta. For odd-sun-free (OSF)-chordal graphs, the upper bound can be reduced to lambda(G) less than or equal to 2 Delta + 1. For sun-free (SF)-chordal graphs, the upper bound can be reduced to lambda(G) less than or equal to Delta + 2 chi(G) - 2. Finally, we present a polynomial time algorithm to determine lambda(T) for a tree T.