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 15 of 15 for “"Structural Graph Theory"”.
-
Some Problems in Structural Graph Theory
For a complete bipartite graph Ks,t, the total number of edges st may not be a triangular number; that is, there may exist 0 < ℓ ≤ n such that e(G) = 1 + 2 + 3 + ··· + n + ℓ. A new question is, can we still decompose the graph Ks,t into distinct paths of lengths 1, …
-
Five Topics in Extremal and Structural Graph Theory
The Friendship Theorem states that if G is a graph in which every two vertices have exactly one common neighbor, then G has a dominating vertex. Sos defined an analogous friendship property for 3-uniform hypergraphs, and constructed a family satisfying it. We present additional 3-uniform …
-
Testing, Learning, Sampling, Sketching
… of research in property testing and learning theory. The first is to understand the relationship between testing and learning, and the second is to develop efficient testing and learning algorithms. We present results towards both goals. - An oft-repeated motivation for property testing …
-
From graph minor theory to 3-dimensions
… projects from topological combinatorics and structural graph theory. Firstly, we extend Heawood's theorem on the colourability of plane triangulations to triangulations of 3-space by proving that a triangulation of 3-space can be edge coloured with three colours if and only if all edges have …
-
Subdivisions of complete graphs
A subdivision of a graph G, also known as a topological G and denoted by TG, is a graph obtained from G by replacing certain edges of G with internally vertex-disjoint paths. This dissertation studies a problem in structural graph theory regarding subdivisions of a complete graph in graphs. In this …
-
Graph-Based Alignment of Heterogeneous Tracking Events - A Process Mining and Structural Time Warping Approach to Canonicalizing Shipment Lifecycles
… methodology integrates process mining with structural graph theory. First, an optional pre-processing layer utilizes the HeuristicsMiner algorithm to isolate the main underlying process from noise, outliers, and low-frequency traces. Next, the pipeline usesWeisfeiler-Lehman (WL) subtree …
-
Algebraic and semi-algebraic invariants on quadrics
… terms of properties on the corresponding simple graphs. Our main theorem is the graph decomposition theorem that provides a bound on the regularity of a quadratic monomial ideal. By combining the main theorem with results in structural graph theory, we proved, improved, and generalized many of …
-
Model-theoretic considerations in finite combinatorics
… that lie primarily in the intersection of model theory and finite combinatorics. The two main areas of combinatorics that make an appearance in the pages to follow are Structural Ramsey Theory and Extremal Graph Theory. Chapter 3 focusses on interactions between model theory and structural Ramsey …
-
Cycles and coloring in graphs and digraphs
… areas related to extremal problems in directed graphs. The first concerns a rainbow generalization of the Caccetta-H\"{a}ggkvist conjecture, made by Aharoni. The Caccetta-H\"{a}ggkvist conjecture states that if $G$ is a simple digraph on $n$ vertices with minimum out-degree at least $k$, then …
-
Cyclically 5-Connected Graphs
… states that every bridgeless, Petersen-free graph admits a nowhere-zero 4-flow. This hard conjecture has been open for over half a century with no significant progress in the first forty years. In the recent decades, Robertson, Thomas, Sanders and Seymour has proved the cubic version of this …
-
Chronological rectangle digraphs
Interval graphs admit elegant ordering and structural characterizations. A natural digraph analogue of interval graphs, called chronological interval digraphs, has recently been identified and studied. We introduce the class of chronological rectangle digraphs, and show that they are a higher …
-
Circle Graph Obstructions
… characterization of the class of circle graphs. The proof uses signed graphs and is analogous to Gerards’ graphic proof of Tutte’s excluded-minor characterization of the class of graphic matroids.
-
Analyzing Tree Attachments in 2-Crossing-Critical Graphs with a V8 Minor
The crossing number of a graph is the minimum number of pairwise edge crossings in a drawing of the graph in the plane. A graph G is k-crossing-critical if its crossing number is at least k and if every proper subgraph H of G has crossing number less than k. It follows directly from Kuratowski's …
-
Viewing extremal and structural problems through a probabilistic lens
… probability to solve problems from extremal and structural combinatorics. The main problem in Chapter 2 is determining the typical structure of $t$-intersecting families in various settings and enumerating such systems. The analogous sparse random versions of our extremal results are also …
-
On the independent spanning tree conjectures and related problems
… (edge-)disjoint. The relationship between graph (edge-)connectivity and the existence of (edge-)independent spanning trees is explored. The (Edge-)Independent Spanning Tree Conjecture states that every k-(edge-)connected graph has k-(edge-)independent spanning trees with arbitrary root. We …