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.