Fall 2005 Seminar Series

DATE: Thursday, October 13, 2005
LOCATION: E40-298
TIME: 4:15pm
Reception immediately following in the Philip M. Morse Reading Room, E40-106

SPEAKER:
Kourosh Eshghi
Associate Professor
Industrial Engineering Department
Sharif University of Technology

TITLE
Graceful Graphs

ABSTRACT
A graceful labeling of a graph G = (V, E) with n vertices and m edges is a one-to-one mapping Y of the vertex set V(G) into the set {0, 1, 2, . , m} with this property: If we define, for any edge e = (u, v) Î E(G), the value W (e) = ½ Y (u)- Y (v) ½ then W is a one-to-one mapping of the set E(G) onto the set {1, 2, . , m}. A graph is called graceful if it has a graceful labeling. In this lecture , first we summarize much of what is known about graceful graphs. Then we discuss some applications of graceful graphs in decomposition of graphs and integer sequences. The existence of graceful labelings of special classes of quadratic graphs with some isomorphic components is also discussed. Despite the large number of papers published on the subject of graph labeling, there are few particular techniques to use by researchers to gracefully label graphs. In the last part of this lecture, a new approach based on the mathematical programming technique is presented to model and solve the graceful labeling problem.