2013/06/12 by Shamik Ghosh, Ghosh, Shamik
Computer Science · Mathematics · #05C78 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO #msc:05C78
paper · pdf · doi:10.48550/arxiv.1306.2932
23 pages, 15 figures
arxiv created 2013/06/28 · arxiv updated 2013/07/01
A graph G=(V,E) with m edges is graceful if it has a distinct vertex labeling f, a map from V into the set0,1,2,3,...,m which induces a distinct edge labeling |f(u)-f(v)| for edges uv in E. The famous Ringel-Kotzig conjecture (1964) is that all trees are graceful. The base of a tree T is obtained from T by deleting its one-degree vertices. A caterpillar is a tree whose base is a path and a lobster is a tree whose base is a caterpillar. Paths and caterpillars are known to be graceful. Next it was conjectured by Bermond (1979) that all lobsters are graceful. In this paper we describe various methods of joining graceful graphs and α-labeled graphs using the adjacency matrix characterization that initiated by Bloom (1979) and others. We apply these results to obtain some classes of graceful lobsters and indicate how to obtain some others.