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"”.
-
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 …
-
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 …
-
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 …
-
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
-
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
-
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 …
-
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.
-
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''. …
-
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 …
-
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 …
-
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 …
-
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> …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
Page 1 of 2