Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 7 of 7 for “"cycles in graphs"”.
-
Extremal problems for cycles in graphs and hypergraphs
In this thesis, we study several generalizations of Turan type problems in graphs and hypergraphs. In particular, we focus on graphs and hypergraphs without long cycles or long paths, extending famous results of Erdos and Gallai. Results include bounds on the size of such objects as well as …
-
The Configuration Space of Two Particles Moving on a Graph
In this thesis we study the configuration space, F (Γ, 2), of two particles moving without collisions on a graph Γ with a view to calculating the Betti numbers of this space. We develop an intersection theory for cycles in graphs inspired by the classical intersection theory for cycles in manifolds …
-
Exploiting structure to cope with NP-hard graph problems: Polynomial and exponential time exact algorithms
An ideal algorithm for solving a particular problem always finds an optimal solution, finds such a solution for every possible instance, and finds it in polynomial time. When dealing with NP-hard problems, algorithms can only be expected to possess at most two out of these three desirable …
-
Erdos-Posa theorems for undirected group-labelled graphs
Erdős and Pósa proved in 1965 that cycles satisfy an approximate packing-covering duality. Finding analogous approximate dualities for other families of graphs has since become a highly active area of research due in part to its algorithmic applications. In this thesis we investigate the Erdős-Pósa …
-
Extremal Problems for Cycles, Paths and Set-Systems
This thesis consists of an introduction and five chapters, each devoted to a different combinatorial problem. What ties all problems considered in this thesis together is their extremal nature and the probabilistic point of view taken in their formulations or analysis. In the first three chapters …
-
Extremal problems in disjoint cycles and graph saturation
In this thesis, we tackle two main themes: sufficient conditions for the existence of particular subgraphs in a graph, and variations on graph saturation. Determining whether a graph contains a certain subgraph is a computationally difficult problem; as such, sufficient conditions for the existence …