DECOMPOSITIONS INTO LINEAR FORESTS AND DIFFERENCE LABELINGS OF GRAPHS

Difference labelings of a graph are realized by assigning distinct int eger values to each vertex and then associating with each edge uv, the absolute difference of those values assigned to its endvertices u and v. Labelings of this type include bandsize labelings, in which the ca rdinality of the edge label set is minimized, and graceful labelings, in which the cardinality of the edge label set equals the number of ed ges. Three new classes of difference labeling problems are defined her e, based on the fact that the subsets of edges with common edge labels form linear forests that partition the edge set. In particular, the f ollowing three questions are addressed: (1) Given graph G with edge se t E(G) and a decomposition D of G into linear forests, does there exis t a labeling of the vertices of G for which D is a common-weight decom position? (2) Given graph G with edge set E(G) and a collection of lin ear forests F1, F2, ..., F(k) containing a total of Absolute value of E edges, does there exist a common-weight decomposition of G whose par ts are respectively isomorphic to F1, F2, ..., F(k)? (3) Given graph G with edge set E(G) and a set of integers m1, m2, ..., m(k) whose sum is Absolute value of E, does there exist a common-weight decomposition of G whose parts contain ]E(i)\ = m(i) (1 less-than-or-equal-to i les s-than-or-equal-to k) edges? Answers to these questions for certain cl asses of graphs are found, tools for studying these questions are deve loped, and some open problems are formulated.