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"”.

  1. 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 …

    fu-berlin Repository record for On Hamilton cycles and other spanning structures (opens in a new tab)

  2. 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 …

    birmingham Download PDF for Hamilton cycles in large graphs and hypergraphs: existence and counting (opens in a new tab)

  3. 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 …

    birmingham Download PDF for Packings and coverings with Hamilton cycles and on-line Ramsey theory (opens in a new tab)

  4. 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 …

    birmingham Download PDF for Embedding problems in graphs and hypergraphs (opens in a new tab)

  5. Σχεδιασμός και ανάλυση αλγορίθμων για τυχαία και εξελικτικά δίκτυα

    … 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 …

    greece Repository record for Σχεδιασμός και ανάλυση αλγορίθμων για τυχαία και εξελικτικά δίκτυα (opens in a new tab)

  6. 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 …

    guelph Repository record for Investigating the Use of Perfecting Matching in an Algorithm to Detect Non-Hamiltonicity of Snarks (opens in a new tab)

  7. 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$ …

    birmingham Download PDF for Packing and embedding large subgraphs (opens in a new tab)

  8. 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 …

    birmingham Download PDF for Local approaches to global problems in extremal combinatorics (opens in a new tab)

  9. 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 …

    birmingham Download PDF for Path and cycle decompositions of graphs and digraphs (opens in a new tab)

  10. 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 …

    uvic Repository record for A compactness theorem for Hamilton circles in infinite graphs (opens in a new tab)

  11. 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 …

    birmingham Download PDF for Extremal graph theory via structural analysis (opens in a new tab)

  12. 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 …

    birmingham Download PDF for Substructures in large graphs (opens in a new tab)

  13. 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 …

    birmingham Download PDF for Embedding spanning structures in graphs and hypergraphs (opens in a new tab)

  14. 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 …

    nebraska Repository record for Graphs with Few Spanning Substructures (opens in a new tab)

  15. 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 …

    unsw Repository record for Asymptotic enumeration of sparse uniform hypergraphs, with applications (opens in a new tab)

  16. 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 …

    birmingham Download PDF for Large structures in dense directed graphs (opens in a new tab)

  17. Absorptions in combinatorics

    … result for Ahroni's conjecture on transversal Hamilton cycles.</p>

    oxford Repository record for Absorptions in combinatorics (opens in a new tab)

  18. 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 …

    mtu Repository record for Hamilton decompositions of 6-regular abelian Cayley graphs (opens in a new tab)

  19. 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$. …

    clemson Repository record for A set of tournaments with many Hamiltonian cycles (opens in a new tab)

Page 1 of 2