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"”.

  1. 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 < &ell; &le; n such that e(G) = 1 + 2 + 3 + &middot;&middot;&middot; + n + &ell;. A new question is, can we still decompose the graph Ks,t into distinct paths of lengths 1, …

    uiuc Repository record for Some Problems in Structural Graph Theory (opens in a new tab)

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

    uiuc Repository record for Five Topics in Extremal and Structural Graph Theory (opens in a new tab)

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

    waterloo Repository record for Testing, Learning, Sampling, Sketching (opens in a new tab)

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

    birmingham Download PDF for From graph minor theory to 3-dimensions (opens in a new tab)

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

    gatech Repository record for Subdivisions of complete graphs (opens in a new tab)

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

    chalmers Repository record for Graph-Based Alignment of Heterogeneous Tracking Events - A Process Mining and Structural Time Warping Approach to Canonicalizing Shipment Lifecycles (opens in a new tab)

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

    gatech Repository record for Algebraic and semi-algebraic invariants on quadrics (opens in a new tab)

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

    whiterose Download PDF for Model-theoretic considerations in finite combinatorics (opens in a new tab)

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

    waterloo Repository record for Cycles and coloring in graphs and digraphs (opens in a new tab)

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

    waterloo Repository record for Cyclically 5-Connected Graphs (opens in a new tab)

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

    uvic Repository record for Chronological rectangle digraphs (opens in a new tab)

  12. 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.

    waterloo Repository record for Circle Graph Obstructions (opens in a new tab)

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

    waterloo Repository record for Analyzing Tree Attachments in 2-Crossing-Critical Graphs with a V8 Minor (opens in a new tab)

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

    uiuc Repository record for Viewing extremal and structural problems through a probabilistic lens (opens in a new tab)

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

    gatech Repository record for On the independent spanning tree conjectures and related problems (opens in a new tab)