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"”.
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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>
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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. …
-
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 …
-
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, …
-
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 …
-
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 …
Page 1 of 4