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 20 for “"Hamilton cycle"”.
-
On the Existence of a Second Hamilton Cycle in Hamiltonian Graphs With Symmetry
… Sheehan conjectured that every simple 4-regular hamiltonian graph has a second Hamilton cycle. If Sheehan's Conjecture holds, then the result can be extended to all simple d-regular hamiltonian graphs with d at least 3. First, we survey some previous results which verify the existence of a second …
-
On Hamilton cycle decompositions of complete multipartite graphs which are both cyclic and symmetric
Let G be a graph with v vertices. A Hamilton cycle of a graph is a collection of edges which create a cycle using every vertex. A Hamilton cycle decomposition is cyclic if the set of cycle is invariant under a full length permutation of the vertex set. We say a decomposition is symmetric if all the …
-
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 …
-
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 …
-
On cycles in directed graphs
… at least 3 |G| / 8 + alpha |G| contains a Hamilton cycle. This gives an approximate solution to a problem of Thomassen. Furthermore, answering completely a conjecture of Haggkvist and Thomason, we show that we get every possible orientation of a Hamilton cycle. We also deal extensively with …
-
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 …
-
Robust expansion and hamiltonicity
… of robust expansion, and the classical notion of Hamiltonicity. In Chapter 2 we prove that every sufficiently large ‘robustly expanding’ digraph which is dense and regular has an approximate Hamilton decomposition. This provides a common generalisation of several previous results and in turn was a …
-
Τυχαίες συνδυαστικές δομές
… intersection graph G (n,m,p) contains or not a Hamilton cycle. We assume that the parameter p of the model is such that p=p (n,m). We show that for the range of n,m,p which the model is not trivial or equivalent to other models the graph property contains a Hamilton cycle, exhibits sharp …
-
Restricted 2-factors in bipartite graphs
… a spanning subgraph consisting of disjoint cycles with no cycle of length less than or equal to k. It is a generalization of the well known Hamilton cycle problem and is equivalent to this problem when n2≤k≤n-1 . This paper considers necessary and sufficient conditions, algorithms, and …
-
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 …
-
Independent domination critical graphs
… the maximum possible diameter. We also explore Hamiltonian properties of edge independent domination critical graphs by proving that every 2-connected edge independent domination critical graph with independent domination number three has a Hamilton cycle. We then develop a complete …
-
Paths and cycles in graphs and hypergraphs
… hypergraph theory all of which feature paths or cycles. A \(k\)-uniform tight cycle \(C^{(k)}_n\) is a \(k\)-uniform hypergraph on \(n\) vertices with a cyclic ordering of its vertices such that the edges are all \(k\)-sets of consecutive vertices in the ordering. We consider a generalisation of …
-
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$ …
-
Extremal and probabilistic problems for discrete structures
… ensures a 2-edge-coloured graph G contains a Hamilton cycle with large discrepancy, that is, a Hamilton cycle with significantly more than half of its edges in one colour. We prove an analogous result for r-colourings. The second topic is the study of Dirac-type problems for (vertex) ordered …
-
Σχεδιασμός και ανάλυση αλγορίθμων για τυχαία και εξελικτικά δίκτυα
… 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 …
-
Eulerian Properties of Design Hypergraphs and Hypergraphs with Small Edge Cuts
… have produced results about rank-2 universal cycles and 1-overlap cycles, which are equivalent to our definition of Euler tours. In contrast, an Euler family is a collection of nontrivial closed walks that jointly traverse every edge of the hypergraph exactly once and cannot be concatenated …
-
Gray code numbers of complete multipartite graphs
… exactly one vertex differently. We explore the Hamiltonicity and connectivity of such graphs, with particular focus on the k-colouring graphs of complete multipartite graphs. We determine the connectivity of the k-colouring graph of the complete graph on n vertices for all n, and show that the …
-
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 …