Graph Labeling And Non Separating Trees

This dissertation studies two independent problems, one is about graph labeling and the other problem is related to connectivity condition in a simple graph. Graph labeling is a rapidly developing area of research in graph theory, having connections with a variety of application-oriented areas such as VLSI optimization, data structures and data representation. Furthermore, the connectivity conditions in a simple graphs may help us to study the new aspects of ad hoc networks, social networks and web graphs. In chapter 2, we study path systems, reduced path systems and how to construct a super edge-graceful tree with any number of edges using path systems. First, we give an algorithm to reduce a labeled path system to a smaller labeled path system of a dierent type. First, we investigate the cases (m; k) = (3; 5) and (m; k) = (4; 7), where m is the number of paths and 2k is the length of each path, and then we give a generalization for any k;m = 3 and m = 4. We also describe a procedure to construct a super-edge-graceful tree with any number of edges. In chapter 3, we study connected graphs with certain distance-degree condition and find characteristics of a subtree of the graph whose deletion does not disconnect the graph. If T is a tree on n vertices, n > 3, and if G is a connected graph such that d (u) + d (v) + d (u; v) > 2n for every pair of distinct vertices of G, it has been conjectured that G must have a non-separating copy of T. We prove a result for the special case in which d (u)+d (v)+d (u; v) > 2n+2 for every pair of distinct vertices of G, and improve this slightly for trees of diameter at least four and for some trees of diameter three. In chapter 4, we characterize the graphs on at most 8 vertices with d (u) + d (v) + d (u; v) > 7 for every pair of distinct vertices of G, and no non-separating copy of K1;3. we also study several algorithms used to verify Locke's conjecture for a special case of non-separating trees of size k in any connected 2k-cohesive graph up to 9 vertices.