Graceful Kayak Paddles

Abstract

A kayak paddle is a graph made of two cycles joined by a path. We can define KP(r, s, l) as two cycles of lengths r and s joined by a path of length l. If a graph G has m vertices and n edges, then a general vertex labeling of the graph is a one-to-one mapping of the vertex set of G into the set of all non-negative integers. If we have two vertices, say x and y joined by an edge xy, we define the edge length as min{x − y, y − x}, where the subtraction is performed in Z2n+1. Two important types of vertex labelings are ρ- and β- labelings. In a ρ- or rosy labeling the vertices must be within the set {0, 1, . . . , 2n} and the set of the edge lengths must be equal to {1, 2, . . . ,n}. A β- or graceful labeling is a ρ-labeling where all the vertex labels must come from {0, 1, . . . ,n}, and the set of edge lengths must be equal to {1, . . . ,n}. If a graph can be labeled using either a rosy labeling or a β-labeling, then it can cyclically decompose K2n+1. D. Froncek and L. Tollefson proved results for kayak paddles decomposing a complete graph using rosy labelings. In this thesis we investigate the existence of graceful labelings of kayak paddles.