Paths and cycles (Graph theory)

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.