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 64 for “"Induced subgraph"”.

  1. Partitioning algorithms for induced subgraph problems

    … NP-hard problems that involve finding a large induced subgraph contained by each of two input graphs: the induced subgraph isomorphism problem and the maximum common induced subgraph problem. The MCSPLIT algorithms resemble forward-checking constrant programming algorithms, but use …

    glasgow Repository record for Partitioning algorithms for induced subgraph problems (opens in a new tab) Download PDF for Partitioning algorithms for induced subgraph problems (opens in a new tab)

  2. Unavoidable Structures in Large and Infinite Graphs

    … large 2-connected graphs. For the relation of induced subgraphs, Ramsey proved that for every positive integer r, every sufficiently large graph contains as an induced subgraph either Kr or Kr. It is well known that, for every positive integer r, every sufficiently large connected graph …

    lsu-thes Repository record for Unavoidable Structures in Large and Infinite Graphs (opens in a new tab)

  3. On Unavoidable Infinite Hypergraphs

    … contains either K∞ or $\overline{K∞}$ as an induced subgraph. For this reason, K∞ and $\overline{K∞}$ are often referred to as the unavoidable infinite graphs. Many similar results have characterized the unavoidable members for various classes of infinite graphs; perhaps the most notable of …

    lsu-thes Repository record for On Unavoidable Infinite Hypergraphs (opens in a new tab)

  4. Bounding the Number of Graphs Containing Very Long Induced Paths

    Induced graphs are used to describe the structure of a graph, one such type of induced graph that has been studied are long paths. <p>In this thesis we show a way to represent such graphs in terms of an array with two colors and a labeled graph. Using this representation and the techniques of Polya …

    byu Repository record for Bounding the Number of Graphs Containing Very Long Induced Paths (opens in a new tab) Download PDF for Bounding the Number of Graphs Containing Very Long Induced Paths (opens in a new tab)

  5. Characterizations of Certain Classes of Graphs and Matroids

    … geometries. A graph in which every connected induced subgraph has a disconnected complement is called a cograph. Such graphs are precisely the graphs that do not have the 4-vertex path as an induced subgraph. In Chapter 3, we define a 2-cograph to be a graph in which the complement of every …

    lsu-thes Repository record for Characterizations of Certain Classes of Graphs and Matroids (opens in a new tab)

  6. Excluded Structures for Pinch-graphic Matroids and Tournaments

    … For tournaments, we bound the size of excluded induced subgraphs of k-degenerate tournaments and we bound the number of backedge graphs of a tournament that are P3-free or Kt-free. Furthermore, we introduce a new way to color the arcs of a tournament and we propose a conjecture that connects …

    waterloo Repository record for Excluded Structures for Pinch-graphic Matroids and Tournaments (opens in a new tab)

  7. Foreshadowing the Grid Theorem for Induced Subgraphs

    … toward a complete description of the unavoidable induced subgraphs of graphs with large treewidth. This is motivated by the Grid Theorem of Robertson and Seymour (1986) which achieves the same goal for minors (and subgraphs). Given a graph class C, we say that C is clean if the only induced …

    waterloo Repository record for Foreshadowing the Grid Theorem for Induced Subgraphs (opens in a new tab)

  8. Sub-optimality of Local Algorithms on Sparse Random Graphs

    … Given some large graph G, find the maximum sized induced subgraph of G whose connected components have size no bigger than T. When T equals 1 this is the problem of finding the maximum independent sets in G. We show that for asymptotically large values of the degree d, local algorithms cannot …

    toronto-retro Repository record for Sub-optimality of Local Algorithms on Sparse Random Graphs (opens in a new tab)

  9. Algorithms for the Maximum Independent Set Problem

    … graph classes defined by a set F of forbidden induced subgraphs. We revise the literature about the issue, for example complexity results, applications, and techniques tackling the problem. Through considering some general approach, we exhibit several cases where the problem admits a …

    qucosa-diss

  10. Skolem sequences: Generalizations and applications

    … graph with v vertices can be embedded as an induced subgraph in a Skolem labelled graph on O(v³) vertices, and show that all paths, cycles and n-windmills can be Skolem labelled or minimum hooked Skolem labelled.</p>

    mcmaster Repository record for Skolem sequences: Generalizations and applications (opens in a new tab)

  11. Structure Mining: Finding Cohesive and Learning-Efficient Subgraphs

    … core connectivity or functionality. To identify subgraphs characterized by high co-occurrence and robustness, this thesis delves into the mining of cohesive subgraphs and learning-efficient subgraphs. Cohesive subgraphs encompass both co-occurrence and robustness, while learning-efficient …

    auckland-ms Repository record for Structure Mining: Finding Cohesive and Learning-Efficient Subgraphs (opens in a new tab)

  12. Induced Saturation Number

    <p>In this paper, we discuss the induced saturation number. It is a nice generalization of the saturation number that will allow us to consider induced subgraphs. We define the induced saturation number of a graph H to be the fewest number of gray edges in a trigraph T such that H does not appear …

    iastate Repository record for Induced Saturation Number (opens in a new tab)

  13. Vertex coloring with forbidden subgraphs

    … if $G$ does not contain any graph in $L$ as induced subgraph. A $hole$ is an induced cycle of length at least $4$. A $hole$-$twin$ is a graph obtained by adding a vertex adjacent to three consecutive vertices in a $hole$. Hole-twins are closely related to the characterization of the line …

    wilfrid-laurier Repository record for Vertex coloring with forbidden subgraphs (opens in a new tab) Download PDF for Vertex coloring with forbidden subgraphs (opens in a new tab)

  14. The 2-Core of a Random Inhomogeneous Hypergraph

    The k-core of a hypergraph is the unique subgraph where all vertices have degree at least k and which is the maximal induced subgraph with this property. We study the 2-core of a random hypergraph by probabilistic analysis of the following edge removal rule: remove any vertices with degree less …

    penn Repository record for The 2-Core of a Random Inhomogeneous Hypergraph (opens in a new tab)

  15. Topics in Graph Compositions

    … element of the partition yields a connected, induced subgraph of G. This dissertation is comprised of 5 chapters. The first is a general introduction to the concept of graph compositions and a survey of previously researched work; the second focuses on the composition number of deletions of …

    wvu Repository record for Topics in Graph Compositions (opens in a new tab)

  16. KE Theory & the Number of Vertices Belonging to All Maximum Independent Sets in a Graph

    … graph $G$, we will show there is a distinguished induced subgraph $G[X]$ such that, under weaker assumptions, $\xi (G) \geq 1 + \alpha (G[X]) - \mu (G[X])$. Furthermore $1 + \alpha (G[X]) - \mu (G[X]) \geq 1 + \alpha (G) - \mu (G)$ and the difference between these bounds can be arbitrarily large. …

    vcu Repository record for KE Theory & the Number of Vertices Belonging to All Maximum Independent Sets in a Graph (opens in a new tab)

  17. Problems in Graph Theory With Applications to Topology and Modeling RNA

    … graph, and give a sufficient forbidden induced subgraph condition for independence number two graphs. In the third project, we extend an existing method and provide a robust framework for studying and analyzing the structure of RNA molecules via chord diagrams and graph theory. In the …

    vcu Repository record for Problems in Graph Theory With Applications to Topology and Modeling RNA (opens in a new tab)

  18. Densest Subgraph Discovery On The CPU

    The Densest Subgraph Discovery (DSD) problem is a prevalent problem in the field of graph mining, aiming to find the cohesive subgraph. Given a graph �� = (��,��) and an integer �� ≥ 2, the goal is to find a vertex sub- set �� ⊆ �� whose induced subgraph �� (��) maximizes the ��-clique density, …

    rowan Repository record for Densest Subgraph Discovery On The CPU (opens in a new tab)

  19. Unavoidable Immersions and Topological Minors of k-edge-connected Graphs

    … r, every sufficiently large graph contains as an induced subgraph either Kr or $\overline{Kr}$. We consider different graph containment relations, focusing primarily on the immersion relation. In the case of finite graphs, we provide the unavoidable immersions of 4-edge-connected graphs and prove …

    lsu-thes Repository record for Unavoidable Immersions and Topological Minors of k-edge-connected Graphs (opens in a new tab)

  20. A Forbidden Subgraph Characterization Problem and a Minimal-Element Subset of Universal Graph Classes

    … paper we show that if each H_i has a forbidden subgraph characterization then the direct sum and join of these H_i also have forbidden subgraph characterizations. We provide various results which in many cases allow us to exactly determine the minimal forbidden subgraphs for such …

    byu Repository record for A Forbidden Subgraph Characterization Problem and a Minimal-Element Subset of Universal Graph Classes (opens in a new tab) Download PDF for A Forbidden Subgraph Characterization Problem and a Minimal-Element Subset of Universal Graph Classes (opens in a new tab)

Page 1 of 4