beta test

We are working with labelings of simple graphs. A graph, G, consists of a set V (G) of vertices and a set E(G) of edges connecting these vertices. We call the graphs simple because they have no loops, edges connecting a vertex to itself, and only one edge can exist between any two vertices. We refer to the size of V (G) by |G|. The degree of a vertex is defined as the number of vertices that vertex shares an edge with. 

A vertex labeling f of a graph G is an assignment of labels to the vertices of G. A vertex labeling f is called a graceful labeling of a graph G with e edges if f is an injection from the vertices of G to the set {0, 1, …, e} such that when each edge UV is assigned the label |f(U) - f(V)| the resulting edge labels are distinct. A graph G is graceful if there exists a graceful labeling of G. We use the terms “label” and “weight” interchangably to denote the label f assigns to a given vertex. We refer to the weight of a vertex V by W(V ).

An alpha-labeling of a graph G (if it exists) is a graceful labeling of G such that along every edge UV of G where U, V are vertices in G, one of U and V has a weight not more than |G|/2 and the other has a weight not less than |G|/2. 

Graceful labeling is one of the best known and most useful methods of graph labeling. Social and communication networks very often resemble trees, a class of graphs that we deal extensively with. It is very useful to have two users (a pair of vertices) uniquely specify a communication link (an edge connecting the two vertices), through a simple subtraction, and conversely, any communication link uniquely corresponds to a pair of users. In addition, graceful labelings apply to the Frequency Assignment Problem, one of the most important problems in radio network engineering, in which cells are assigned a number of frequencies. A limited frequency range means that different cells must reuse frequencies while minimizing interference. As such, by letting each cell be represented by a vertex, our graceful labeling becomes highly applicable in networks that resemble adjoined cycles or trees as we can reference each pair of connected cells uniquely. Our results on graceful labelings of cycle chains also provide insight on labeling the mesh configurations found in cellular networks.

It has been shown that a cycle C is graceful iff |C| is congruent to 0 (mod 4) or 3 (mod 4), and that graceful cycles have alpha-labelings. In this paper, we also look at the graphs formed by adjoining cycles with number of vertices a multiple of 4 at opposite vertices, graphs which we call diamondbacks, as well as graphs formed by adjoining cycles with number of vertices a multiple of 4 at adjacent vertices, or snakes. Our work with diamondbacks and snakes relates to earlier work dealing with showing the existence of a graceful labeling for all uniform quadrilateral snakes, as well as work dealing with certain classes of uniform diamondbacks.

The study of the important field of graceful graphs was introduced by Rosa, who referred to graceful labelings as beta-valuations; the term graceful labeling would be introduced by Golomb several years later. The goal of studying graceful graphs is to prove the existence of graceful labelings for certain families of graphs.

One of the most famous unsolved problems in dealing with graceful graphs is the Graceful Tree Conjecture, also known as the Ringel-Kotzig conjecture, named after Gerhard Ringel and Anton Kotzig, which deals with a large class of graphs known as trees. This conjecture states that all trees are graceful. Although much research has been done over the last three decades, the Ringel-Kotzig conjecture remains unproven. Many steps in different directions have been taken toward the conjecture, however. Specific families of trees have been shown to be graceful. Trees with 35 vertices or less have been shown to be graceful, as well as symmetrical trees and trees with at most 4 end vertices. It has been conjectured that all lobsters, which are trees with vertices at most 2 edges away from a path, are graceful. Trees with diameter 5 or less have also been shown to be graceful.