Locke, Stephen C.

If T is a tree on n vertices, n 3, and if G is a connected graph such that dudvd 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. In this note, we prove this result for the special case in which dudv du,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. We also characterize the graphs on at most 8 vertices with
dudvdu,v 7 for every pair of distinct vertices of G, and no non-separating copy of K_{1,3}

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 different 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.

Determining which graphs are hamiltonian is a central unsolved problem in graph theory. More generally, the study of long cycles in graphs has been extensive, and there are numerous results on the subject in the mathematical literature. In this dissertation, we survey several of these results. The study of long paths is related to the study of long cycles. In a graph in which every pair of vertices is connected by a long path, every edge lies on a long cycle. We prove that any set of four vertices lying on a common path in a 2-connected graph lie on a common long path, generalizing a result of Lovasz. We further exploit the relationship between long paths and long cycles to prove that the cycle spaces of a large class of hamiltonian graphs are generated by long cycles, partially proving a conjecture made by Bondy.

We investigate the game known as Chomp. This is an example of a combinatorial two-person nim-type game. Like most of games it has very simple rules, but this does not mean that there is a simple strategy to win. With the help of a computer program we present winning strategies for the first player, since P1 always wins. We also show an isomorphism between Chomp and the Divisor Game.

Let G be a 2-connected graph with minimum degree d and with at least d + 2 vertices. Suppose that G is not a cycle. Then there is an odd set of cycles, each with length at least d + 1, such that they sum to zero. If G is also non-hamiltonian or bipartite, cycles of length at least 2d can be used.

A cycle double cover (CDC) of a graph G is a collection C of cycles of G such that each edge of G belongs to exactly two members of C. P. D. Seymour conjectured that every 2-edge-connected graph admits a CDC. In a similar way, a path double cover (PDC) of graph G is a collection P of paths of G such that each edge of G belongs to exactly two paths of P. If each vertex of G is an end of exactly two paths of P, then P is called a perfect path double cover (PPDC). J. A. Bondy asked if every simple graph admits a PPDC. In the first part of this thesis, we present some techniques that have been applied to the cycle double cover conjecture and give a detailed study of CDC for some particular graphs. It has been found that this conjecture is true of planar graphs, 3-edge-colorable cubic graphs, Cayley graphs and graphs which have a Hamiltonian path. In the second part of this thesis, we mainly deal with path double covers and their variants. We will see that every simple graph admits a PPDC and the PPDC problem is in class P. A detailed summary about the main results discussed in this thesis is included.

This dissertation studies two independent problems, each related to a special connectivity condition in a simple graph. The first is a distance-degree condition called cohesion. Given a tree T with n vertices, we analyze the minimum integer f(T) = k, in terms of n, for which any connected k-cohesive graph G contains a copy of T, such that G-V(T) is connected. The problem comes from a generalization of an exercise by Lovasz [L7] in which it is shown that f(K2) = 5. Locke, Tracy and Voss [L5] have proved that in general f(T) > 2n, and in the case in which T is a path, equality is attained. Also Locke [L5.1] proved that f(T) < 4n. Here we improve the upper bound to 4n-6 when T is not a path and to 2n + 2 when T has diameter at most 4. In the particular case of K1,3 we show that f(K1,3) = 2n = 8 is attained. The conjecture that remains open is whether f(T) = 2n for any tree T on n vertices. The second problem studied here is a particular case of the well known relation between the path-connectivity and a set of long cycles, which generate the cycle space of a simple graph. The main conjecture in this topic is by Bondy [B1], and states that if G is a 3-connected graph, with minimum degree at least d and with at least 2d vertices, then every cycle of G can be written as the symmetric difference of an odd number of cycles, each of whose lengths are at least 2d-1. Hartman [H2], Locke [L1, L2, L3], Barovich [BL] and Teng [L6] have proved results related to this conjecture. Here we show that 2-connected, 6-path-connected graphs with at least 9 vertices and minimum degree at least 3 are 6-generated. And more generally, we prove that if a graph G is 2-connected, k-path-connected, and contains a long cycle, then G is (k + 1)-generated, up to some cases which are characterized. The conjecture [L3] of whether, for some constant m, 1/2 < m < 1, every k-path-connected graph is mk-generated, remains open.