Labeling of Graphs and Hypergraphs

Abstract

An undirected graph G is said to be simple if it has no multi-edges and self-loops. If G is connected and has no cycles, it is called an acyclic graph or simply a tree. Labeling (or valuation) of a graph is a map that carries graph elements (vertices and edges) to numbers (usually positive integers). If a labeling uses the vertex-set (edge-set) only then it becomes a vertex-labeling (an edge-labeling), respectively. Labeling is called total if the domain consists of both vertex and edge sets. There are many types of graph labeling but this study emphasizes on antimagic and odd graceful labelings. Kotzig and Rosa have conjectured in a paper that every tree is edge-magic. Later on, Enomoto, Llado, Nakamigawa and Ringel have proposed the conjecture that every tree is a super (a, d)-edge-antimagic total graph when d = 0. Lee and Shah tried to prove this conjecture using computer but failed, they were able to verify it on trees of at most seventeen vertices. The current study is mainly devoted to investigate a super (a, d)-edge-antimagic total labeling of various subclasses of trees: subdivided stars, subdivided caterpillars and exten- ded w-trees. It is also proved that for different values of d the disjoint union of isomorphic and non-isomorphic copies of extended w-trees are super (a, d)-edge-antimagic total. Moreover, the existence of an odd graceful labeling is determined on disjoint union of cycles and paths. Hypergraphs are natural extension of graphs in which elements correspond to nodes (vertices), sets correspond to the edges which are allowed to connect more than two nodes. In this dissertation, a general idea related to the construction of linear h-uniform star hypergraphs is given and it is proved that disjoint union of h-uniform star hypergraphs admits an antimagic vertex labeling.