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 42 for “"Hamiltonicity"”.

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

    birmingham Download PDF for Robust expansion and hamiltonicity (opens in a new tab)

  2. Hamiltonicity problems in random graphs

    … First, we show a very recent development about Hamiltonicity in random subgraphs of the hypercube, where we have resolved a long standing conjecture dating back to the 1980s. Second, we present some original results about correlations between the appearance of edges in random regular …

    birmingham Download PDF for Hamiltonicity problems in random graphs (opens in a new tab)

  3. Hamiltonicity of certain vertex symmetric graphs

    … parallel architectures. In this thesis, we study Hamiltonicity in specific families of Cayley graphs and vertex symmetric graphs. In the first part of the thesis, we study the Hamiltonicity in Faber-Moore digraphs. Faber-Moore digraphs have been proposed as a method of efficient parallel …

    uvic Repository record for Hamiltonicity of certain vertex symmetric graphs (opens in a new tab)

  4. On the Hamiltonicity of Subgroup Lattices

    In this paper we discuss the Hamiltonicity of the subgroup lattices of different classes of groups. We provide sufficient conditions for the Hamiltonicity of the subgroup lattices of cube-free abelian groups. We also prove the non-Hamiltonicity of the subgroup lattices of dihedral and dicyclic …

    mo-state Repository record for On the Hamiltonicity of Subgroup Lattices (opens in a new tab)

  5. Hamiltonicity, Pancyclicity, and Cycle Extendability in Graphs

    … of graphs possessing conditions sufficient for Hamiltonicity: A non-Hamiltonian cycle in a graph with a property that guarantees it is Hamiltonian also guarantees it is cycle extendable. A graph H is an induced subgraph of another graph G if H can be obtained from G by deleting vertices. A graph …

    utahstate Repository record for Hamiltonicity, Pancyclicity, and Cycle Extendability in Graphs (opens in a new tab)

  6. Eulerian subgraphs and Hamiltonicity of claw -free graphs

    Let C(l, k) denote the class of 2-edge-connected graphs of order n such that a graph G ∈ C(l, k) if and only if for every edge cut S ⊆ E(G) with |S| ≤ 3, each component of G - S has order at least n-kl . We prove that If G ∈ C(6, 0), then G is supereulerian if and only if G cannot be contracted to …

    wvu Repository record for Eulerian subgraphs and Hamiltonicity of claw -free graphs (opens in a new tab)

  7. Combinatorial Generalizations of Sieve Methods and Characterizing Hamiltonicity via Induced Subgraphs

    … finite spaces. Finding sufficient conditions for Hamiltonicity in graphs is a classical topic, where the difficulty is bracketed by the NP-hardness of the associated decision problem. The second part of the thesis, consisting of Chapter 4, aims to characterize Hamiltonicity by means of induced …

    waterloo Repository record for Combinatorial Generalizations of Sieve Methods and Characterizing Hamiltonicity via Induced Subgraphs (opens in a new tab)

  8. Enumeration, isomorphism and Hamiltonicity of Cayley graphs: 2-generated and cubic

    … were tested for various properties including Hamiltonicity and diameter. These results are available on the internet in easy to read tables. The motivation for the testing of Cayley graphs for Hamiltonicity was the conjecture that states that every connected Cayley graph is Hamiltonian. New …

    uvic Repository record for Enumeration, isomorphism and Hamiltonicity of Cayley graphs: 2-generated and cubic (opens in a new tab)

  9. Extremal Problems in Graph Theory: Hamiltonicity, Minimum Vertex -Diameter -2 -Critical Graphs and Decomposition

    A star, K1,s, is the complete bipartite graph whose partite sets have size 1 and s, respectively. A graph G has the t-star property if every t vertices of G belong to a subgraph which is a star. Erdo&huml;s, Sauer, Schaer, and Spencer [ESSS] defined f(t, k) to be the minimum n such that the …

    uiuc Repository record for Extremal Problems in Graph Theory: Hamiltonicity, Minimum Vertex -Diameter -2 -Critical Graphs and Decomposition (opens in a new tab)

  10. Investigating the Use of Perfecting Matching in an Algorithm to Detect Non-Hamiltonicity of Snarks

    … The algorithm attempts to decide a graph's non-Hamiltonicity by checking for the non-existence of these permutation matrices using the bipartite matching algorithm. A small collection of snarks are tested and the algorithm correctly identifies these graphs as non-Hamiltonian.

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

  11. Hamiltonian cycles in subset and subspace graphs.

    In this dissertation we study the Hamiltonicity and the uniform-Hamiltonicity of subset graphs, subspace graphs, and their associated bipartite graphs. In 1995 paper "The Subset-Subspace Analogy," Kung states the subspace version of a conjecture. The study of this problem led to a more general …

    unt Repository record for Hamiltonian cycles in subset and subspace graphs. (opens in a new tab)

  12. Two Results in Drawing Graphs on Surfaces

    … drawn on non-planar surfaces and results on edge-hamiltonicity of graphs on the Klein bottle. We first give an infinite family of graphs that are 2-crossing-critical on the projective plane. Using this result, we construct 2-crossing-critical graphs for each non-orientable surface. Next, we use …

    lsu-thes Repository record for Two Results in Drawing Graphs on Surfaces (opens in a new tab)

  13. Hamiltonian Subgroup Graphs

    … are unknown. In this thesis we investigate the hamiltonicity of subgroup graphs, focusing primarily on rank 3 finite abelian p-group, proving that many of them have hamiltonian subgroup graphs. We also present a number of groups which do not have hamiltonian subgroup graphs, a complete …

    mo-state Repository record for Hamiltonian Subgroup Graphs (opens in a new tab)

  14. Combinatorial Properties of Polyiamonds

    … and so three-polytopal, a result on Hamiltonicity, and constructions that use minimal numbers of triangles in realizing four-vectors.

    cuny-grad Repository record for Combinatorial Properties of Polyiamonds (opens in a new tab)

  15. On Hamilton cycles and other spanning structures

    … for the threshold bias in the Maker-Breaker Hamiltonicity game on G(n,p), hitting time thresholds for the appearance of certain spanning trees in the random graph process, and generalizations of the well-known theorems of Ore and Dirac to hypergraphs.

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

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

  17. On Berge Pancyclicity for Uniform Hypergraphs

    … $3\leq k \leq n$. Dirac's classical result on hamiltonicity states that if an $n$-vertex graph $G$ has minimum degree $\delta(G)\geq \frac{n}{2}$, then $G$ is hamiltonian. Under the same minimum degree condition as Dirac, J. A. Bondy showed that $G$ must also be pancyclic or the exceptional …

    south-carolina Repository record for On Berge Pancyclicity for Uniform Hypergraphs (opens in a new tab)

Page 1 of 3