Abstract of Colloquium talk at Math Department of WVU, September 18, 1997

Professor Chuanping Chen

Academia Sinica and University of Texas at Austin

Some new results on construction problems of graphs

Result 1. Let G=(V,E) be a graph with vertex V and edge set E, and f and g two integer-valued functions defined on V. Then we call a spanning subgraph H of G a (g,f)-factor of G if the degree of x in H is not less than g(x), and not greater than f(x) for each vertex x of G. A (g,f)-factorization of G is a partition of E into edge-disjoint (g,f)-factors. Let F(G) be a factorization of G, and F(G) contains m elements F(1),F(2)...,F(m). Let H be a subgraph of G. If F(i) has exactly one edge in common with H for i=1,2,...,m, then we say that F(G) is orthogonal to H. It is proved that every (mg+k,mf-k)-graph contains a subgraph R such that R has a(g,f)-factorization orthogonal to a given subgraph with k edges, where m and k are positive integers with k is less than m and g(x) is nonnegative function on V.

Result 2. Let G be a 2(k+1)-connected graph of order n. It is proved that if for any nonadjacent vertices u and v in G we have max(d(u),d(v)) is not less than n/2 + 2k, then G contains k+1 pairwise disjoint Hamiltonian cycles when minimum degree of G is not less than 4k+3.

The talk will be aimed at a general mathematical audience.