A study on bandwidth and antimagic labelings of trees and decomposition of complete graphs into trees using new graph labelings

Abstract

This thesis pertains to the study of three different major graph newlinelabelings. The first type of labelings are newly defined labelings called and#119896; newlinegraphs and#937; and#8722;labelings and its variation, and#119896; graphs and#937;+ and#8722;labelings which are newlinedefined based on the fundamental and#120588; and#8722;labeling introduced by Alexander Rosa newline(Rosa 1967), and these labelings will be used as tools for obtaining newlinedecomposition of certain complete graphs into trees. The next labeling is the newlinecelebrated Bandwidth Labeling related to Matrix Bandwidth Minimization newlineProblem and the third labeling is the well-known Antimagic Labeling. These newlinetwo labelings are also studied on various classes of trees. newlineIn Chapter 1, an introduction to Graph Decomposition and the newlinenewly defined labelings, and#119896; graphs and#937; and#8722;labelings and and#119896; graphs and#937;+ and#8722;labelings newlineare given. Further, an introduction of each of the other two well-known newlinelabelings, called bandwidth labeling and antimagic labeling, is given, which newlinewould provide enough background for the subsequent chapters. newlineA decomposition of a graph and#119883; into a set of graphs {and#119867;1,and#119867;2,and#8943;,and#119867;and#119905;} is newlinea partition (and#119864;1, and#119864;2, and#8943; ,and#119864;and#119905;) of and#119864;(and#119883;) such that and#9001;and#119864;and#119894;and#9002; and#8773; and#119867;and#119894;, for and#119894;,1 and#8804; and#119894; and#8804; and#119905;, where newlineand#9001;and#119864;and#119894;and#9002; denote the edge induced subgraph induced by the subset of edges and#119864;and#119894; of and#119883;. newlineA graph and#119883; is said to have a (and#119866;1,and#119866;2,and#8943;,and#119866;and#119896;) and#8722;decomposition, if and#119883; can be newlinedecomposed into and#119903;1 copies of and#119866;1, and#119903;2 copies of and#119866;2, and#8943;, and#119903;and#119896; copies of and#119866;and#119896;, where newlineand#65533; newlineand#65533;and#119894; and#8805; 1, for and#119894;,1 and#8804; and#119894; and#8804; and#119896;. newline