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 20 of 21 for “"Hamilton cycles"”.
-
On Hamilton cycles and other spanning structures
… dissertation we present current developments on Hamilton cycles and spanning trees in random graphs as well as in (very) dense hypergraphs. These results include an estimation of the number of Hamilton cycles in G(n,p), existence of an approximately perfect covering of the edge set of a …
-
Hamilton cycles in large graphs and hypergraphs: existence and counting
The study of Hamilton cycles forms a central part of classical graph theory. In this thesis we present our contribution to the modern research on this topic. In Chapter 2, we prove that \( k \)-uniform hypergraphs satisfying a `Dirac-like' condition on the minimum \( (k-1) \)-degree contain many of …
-
Packings and coverings with Hamilton cycles and on-line Ramsey theory
… family. We focus on packings and coverings with Hamilton cycles, and prove the following results in the area. • Let ε > 0, and let \(G\) be a large graph on n vertices with minimum degree at least (1=2+ ε)n. We give a tight lower bound on the size of a maximal packing of \(G\) with edge-disjoint …
-
Embedding problems in graphs and hypergraphs
… The second part of the thesis concerns Hamilton cycles in directed graphs. We give a condition on the degree sequences of a digraph \(G\) that ensures \(G\) is Hamiltonian. This gives an approximate solution to a problem of Nash-Williams concerning a digraph analogue of Chvatal's …
-
Σχεδιασμός και ανάλυση αλγορίθμων για τυχαία και εξελικτικά δίκτυα
… the existence and efficient construction of Hamilton cycles. More specifically, we give an upper bound for the probability $p$ that is needed for almost every random instance $G_{n, m, p}$ of the model to have a Hamilton cycle. We also present two polynomial time, randomized algorithms for …
-
Investigating the Use of Perfecting Matching in an Algorithm to Detect Non-Hamiltonicity of Snarks
The Hamilton cycle decision problem is NP-complete. No polynomial time algorithm that solves this problem is known, and may or may not exist. In this thesis, the co-NP complete non-Hamilton cycle decision problem is investigated via the heuristic O(n^8) weak closure algorithm, with modifications …
-
Packing and embedding large subgraphs
… conjecture that the threshold probability for Hamiltonicity in the random binomial subgraph of the hypercube equals $1/2$. %posed e.g.~by Bollob\'as, In Chapter 2 we obtain the following perturbation result regarding the hypercube $\cQ^n$: if $H\subseteq\cQ^n$ satisfies $\delta(H)\geq\alpha n$ …
-
Local approaches to global problems in extremal combinatorics
… copies of Perfect Matchings, H-factors and Hamilton cycles in large graphs. We then look to random digraphs and consider the D(n, p) model in which each edge is present independently with probability p. We find tail bounds on the size of the largest strongly connected component in the …
-
Path and cycle decompositions of graphs and digraphs
… bipartite tournament can be decomposed into Hamilton cycles. Along the way, we also prove several further results, including a conjecture of Liebenau and Pehova on Hamilton decompositions of dense bipartite digraphs. Secondly, we determine the minimum number of paths required to decompose the …
-
A compactness theorem for Hamilton circles in infinite graphs
The problem of defining cycles in infinite graphs has received much attention in the literature. Diestel and Kuhn have proposed viewing a graph as 1-complex, and defining a topology on the point set of the graph together with its ends. In this setting, a circle in the graph is a homeomorph of the …
-
Extremal graph theory via structural analysis
… minimum codegree close to n/2 which contain a Hamilton 2-cycle. As a corollary we determine the exact Dirac threshold for Hamilton 2-cycles in 4-uniform hypergraphs, and we provide a polynomial-time algorithm which answers the corresponding decision problem for 4-graphs with minimum degree …
-
Substructures in large graphs
The first problem we address concerns Hamilton cycles. Suppose G is a large digraph in which every vertex has in- and outdegree at least |G|/2. We show that G contains every orientation of a Hamilton cycle except, possibly, the antidirected one. The antidirected case was settled by DeBiasio and …
-
Embedding spanning structures in graphs and hypergraphs
… a collection of └\(\delta\)(G)/2┘ edge disjoint Hamilton cycles (plus an additional edge-disjoint matching if \(\delta\)(G) is odd), which confirms for this range of p a conjecture of Frieze and Krivelevich. Secondly, we show that any `robustly expanding' graph with linear minimum degree on …
-
Graphs with Few Spanning Substructures
… determine the complexity of a problem related to Hamilton cycles in hypergraphs. Dirac's theorem states that graphs with minimum degree at least half the size of the vertex set are guaranteed to have a Hamilton cycle. In 1993, Karpinksi, Dahlhaus, and Hajnal proved that for any c < ½, the problem …
-
Asymptotic enumeration of sparse uniform hypergraphs, with applications
… matchings and the expected number of loose Hamilton cycles in random regular uniform hypergraphs. As another application of our first result, we study the average number of uniform spanning hypertrees. Finally, we give a new proof of Blinovsky and Greenhill's asymptotic formula for the …
-
Large structures in dense directed graphs
… graphs which includes all orientations of Hamilton cycles and large subdivisions of any graph. Result (1) confirms a conjecture of Bender and Wormald and settles a conjecture of Havet and Thomassé for almost every tree; (2) strengthens a result of Kühn, Mycroft and Osthus; (3) is a directed …
-
Absorptions in combinatorics
… result for Ahroni's conjecture on transversal Hamilton cycles.</p>
-
Hamilton decompositions of 6-regular abelian Cayley graphs
… every connected, vertex-transitive graph has a Hamilton path. This question has generated a considerable amount of interest, yet remains vastly open. To date, there exist no known connected, vertex-transitive graph that does not possess a Hamilton path. For the Cayley graphs, a subclass of …
-
A set of tournaments with many Hamiltonian cycles
… on $3^n$ vertices, the expected number of Hamiltonian cycles is known to be $(3^n -1)!/2^{3^n}$. Let $T_1$ denote a tournament of three vertices $ {v_1, v_2, v_3}$. Let the orientation be such that there are directed edges from $v_1 $to $v_2$ , from $v_2$ to $v_3$ and from $v_3$ to $ v_1$. …
Page 1 of 2