Browsing by Author "HUANG, KC"

Now showing 1 - 2 of 2

ON PRIME LABELINGS
(1994-03-15)
FU, HL
;
HUANG, KC
;
應用數學系
;
Department of Applied Mathematics
Let G = (V, E) be a graph. A bijection f:V--> {1, 2,...,V} is called a prime labelling if for each e = {u, v} in E, we have GCD(f(u),f(v)) = 1. A graph admits a prime labelling is called a prime graph. Around ten years ago, Roger Entringer conjectured that every tree is prime. So far, this conjecture is still unsolved. In this paper, we show that the conjecture is true for trees of order up to 15, and also show that a few other classes of graphs are prime.
THE LINEAR 2-ARBORICITY OF COMPLETE BIPARTITE GRAPHS
(1994-12-01)
FU, HL
;
HUANG, KC
;
應用數學系
;
Department of Applied Mathematics
A forest in which every component is path is called a path forest. A family of path forests whose edge sets form a partition of the edge set of a graph G is called a path decomposition of a graph G. The minimum number of path forests in a path decomposition of a graph G is the linear arboricity of G and denoted by l(G). If we restrict the number of edges in each path to be at most k then we obtain a special decomposition. The minimum number of path forests in this type of decomposition is called the linear k-arboricity and denoted by la(k)(G). In this paper we concentrate on the special type of path decomposition and we obtain the answers for la2(G) when G is K(n,n). We note here that if we restrict the size to be one, the number la1(G) is just the chromatic index of G.