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 22 for “"Graph theory, combinatorics"”.

  1. On two models of random graphs /

    … asymptotic properties of random intersection graphs are studied. They include birth thresholds for small complete subgraphs in the binomial random intersection graph, the clique number in sparse random intersection graphs and the chromatic index of random uniform hypergraphs. Several new …

    vilnius Repository record for On two models of random graphs / (opens in a new tab)

  2. Erdos-Posa theorems for undirected group-labelled graphs

    … 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 property of various families of constrained cycles and paths by developing new structural tools for …

    gatech Repository record for Erdos-Posa theorems for undirected group-labelled graphs (opens in a new tab)

  3. On word-representability of Apollonian graphs and 1-11-representability of graphs

    A graph G = (V,E) is word-representable if there exists a word w over the alphabet V such that two letters x and y alternate in w if and only if {x, y} ? E. The notion was introduced in the early 2000s by Kitaev and is now the subject of an extensive theory connecting graph theory, combinatorics on …

    strathclyde Repository record for On word-representability of Apollonian graphs and 1-11-representability of graphs (opens in a new tab)

  4. Variations of Turán's theorem

    Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-11-11 without embargo terms

    uiuc Repository record for Variations of Turán's theorem (opens in a new tab)

  5. Extremal problems on special graph colorings

    Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2020-10-02 without embargo terms

    uiuc Repository record for Extremal problems on special graph colorings (opens in a new tab)

  6. A characterization of almost all minimal not nearly planar graphs

    In this dissertation, we study nearly planar graphs, that is, graphs that are edgeless or have an edge whose deletion results in a planar graph. We show that all but finitely many graphs that are not nearly planar and do not contain one particular graph have a well-understood structure based on …

    lsu-thes Repository record for A characterization of almost all minimal not nearly planar graphs (opens in a new tab)

  7. The Apprentices' Tower of Hanoi

    … to optimal algorithms which solve the puzzle. Graph theoretic properties of the associated state graphs are explored. A brief summary of other Tower of Hanoi variants is also presented.

    etsu Repository record for The Apprentices' Tower of Hanoi (opens in a new tab) Download PDF for The Apprentices' Tower of Hanoi (opens in a new tab)

  8. Local Structure for Vertex-Minors

    … about a conjecture of Geelen on the structure of graphs with a forbidden vertex-minor; the conjecture is like the Graph Minors Structure Theorem of Robertson and Seymour but for vertex-minors instead of minors. We take a step towards proving the conjecture by determining the "local structure''. …

    waterloo Repository record for Local Structure for Vertex-Minors (opens in a new tab)

  9. Self-Dual Graphs

    … on constructing and classifying all self-dual graphs and in particular polyhedra. We will give an overview of the recent research in the first two chapters. In the third chapter, we will show the necessary condition that a self-complementary self-dual graph have <i>n</i> ≡ 0, 1 (mod 8) vertices …

    waterloo Repository record for Self-Dual Graphs (opens in a new tab)

  10. Two Results in Drawing Graphs on Surfaces

    … work we present results on crossing-critical graphs 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 …

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

  11. The Non-Backtracking Spectrum of a Graph and Non-Bactracking PageRank

    … centered around non-backtracking walks on graphs. First, we analyze the spectrum of the non-backtracking matrix of a graph. We show how to obtain the eigenvectors of the non-backtracking matrix using a smaller matrix and in doing so, create a block diagonal decomposition which more clearly …

    byu Repository record for The Non-Backtracking Spectrum of a Graph and Non-Bactracking PageRank (opens in a new tab) Download PDF for The Non-Backtracking Spectrum of a Graph and Non-Bactracking PageRank (opens in a new tab)

  12. Hamilton Paths in Generalized Petersen Graphs

    … with <i>k</i> > 2, the generalized Petersen graph, <i>GP</i>(<i>n,k</i>) is Hamilton-laceable if <i>n</i> is even and <i>k</i> is odd, and it is Hamilton-connected otherwise. We take the first step in the proof of this conjecture by proving the case <i>n</i> = 3<i>k</i> + 1 and <i>k</i> …

    waterloo Repository record for Hamilton Paths in Generalized Petersen Graphs (opens in a new tab)

  13. Chromatic polynomials of mixed graphs

    Let G = (V,A,E) be a mixed graph and co : V → {1, 2,...,λ} a function such that co is a proper colouring of the underlying graph, Und(G), and co(u) ≠ co(y) when co(v) = co(x), for every pair of arcs (u,v) and (x,y). Such a function is called a proper oriented λ − colouring of G. The number of …

    uvic Repository record for Chromatic polynomials of mixed graphs (opens in a new tab)

  14. On the Maker-Breaker k-Cycle Game

    … Maker-Breaker k-cycle game on the complete graph for a fixed k ∈ N. This is a special case of Maker-Breaker subraph games that are played by two players called Maker and Breaker who alternately claim edges of the complete graph that were previously unclaimed by either player. Maker wins the …

    cau-kiel Repository record for On the Maker-Breaker k-Cycle Game (opens in a new tab)

  15. Probabilistic Methods

    The Probabilistic Method was primarily used in Combinatorics and pioneered by Erdös Pai, better known to Westerners as Paul Erdos in the 1950s. The probabilistic method is a powerful tool for solving many problems in discrete mathematics, combinatorics and also in graph .theory. It is also very …

    vcu Repository record for Probabilistic Methods (opens in a new tab)

  16. A Graphical Approach to Isospectral Unfoldings

    … techniques used to shrink a matrix, or a graph, into a smaller, dimensionally reduced form while preserving its spectrum. Simple graphs that share isospectral reductions also share quantum walk properties. As such we further develop the inverse process, isospectral unfoldings, to find …

    byu Repository record for A Graphical Approach to Isospectral Unfoldings (opens in a new tab) Download PDF for A Graphical Approach to Isospectral Unfoldings (opens in a new tab)

  17. Localized structure in graph decompositions

    Let v ∈ Z+ and G be a simple graph. A G-decomposition of Kv is a collection F={F1,F2,...,Ft} of subgraphs of Kv such that every edge of Kv occurs in exactlyone of the subgraphs and every graph Fi ∈ F is isomorphic to G. A G-decomposition of Kv is called balanced if each vertex of Kv occurs in the …

    uvic Repository record for Localized structure in graph decompositions (opens in a new tab)

  18. Counting cliques in graphs with excluded minors

    … thesis explores Turán-type extremal problems in graphs that exclude certain minors, focusing on the maximum number of k-cliques such graphs can contain. The first part of the thesis studies planar graphs, which forbid K5 and K3,3 as minors. We determine the maximum number of edges is in a planar …

    gatech Repository record for Counting cliques in graphs with excluded minors (opens in a new tab)

  19. Simple Drawings of Kn from Rotation Systems

    … for i∈[n]. If D is a drawing of a labelled graph, then a rotation at vertex v is the cyclic ordering of the edges at v. In particular, the collection of all vertex rotations of a simple drawing of Kn is a complete rotation system. Can we characterize when a complete rotation system can be …

    waterloo Repository record for Simple Drawings of Kn from Rotation Systems (opens in a new tab)

  20. GoblinCore-64: A scalable, open architecture for data intensive high performance computing

    The current class of mainstream microprocessor architectures rely upon multi-level data caches and relatively low degrees of concurrency to solve a wide range of applications and algorithmic constructs. These mainstream architectures are well suited to efficiently executing applications that are …

    ttu Repository record for GoblinCore-64: A scalable, open architecture for data intensive high performance computing (opens in a new tab)

Page 1 of 2