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 9 of 9 for “"Threshold graph"”.
-
Generalizations of Threshold Graph Dynamical Systems
… propagation in populations that are cast as graphs, where vertices represent agents and edges represent agent interactions. We refer to such formulations as graph dynamical systems. For social applications, threshold models are used extensively for agent state transition rules (i.e., for …
-
Pólya Threshold Graph with infinite and finite memory
This thesis introduces a threshold graph model generated by infinite-memory and finite-memory Pólya urn processes, providing a framework for growing networks with reinforcement effects. In the infinite-memory case, the nodes are sequentially added according to a two-color Pólya urn and the …
-
Extremal results for the number of matchings and independent sets
… answers several questions in extremal graph theory, each concerning the maximum or minimum number of certain substructures a graph can have, given that it must satisfy certain properties. In recent years there has been increased interest in such problems, which are extremal problems for …
-
A Combinatorial Analysis of the Eigenvalues of the Laplacian Matrices of Cographs
Cographs, also known as complement reducible graphs or decomposable graphs, are a recursively defined class of graphs built from a single vertex by the operations of disjoint union and join. The eigenvalues of a cograph's Laplacian matrix are nonnegative integers. In this thesis, we explore the …
-
Graphs with Few Spanning Substructures
… of problems related to spanning substructures of graphs. The first few chapters consider extremal problems related to the number of forest-like structures of a graph. We prove that one can find a threshold graph which contains the minimum number of spanning pseudoforests, as well as rooted …
-
THE SANDPILE & SMITH GROUPS OF CERTAIN CLASSES OF GRAPHS
The Smith group and the sandpile group are graph invariants. In this thesis we compute these groups for a variety of classes of graphs. We provide background materials in Chapter 1. In Chapter 2, on integral circulant graphs, Theorem A provides the Smith group of multiple copies of these graphs. …
-
Edge modification on perfect and reducible graphs with application to watermarking
In graph modification problems, we have to repair, improve, or adjust a graph to satisfy appropriate properties while minimizing the cost of the modification. The study of graph modification problems is crucial to computer science as they find applications in different areas, such as biology, …
-
Chromatic Thresholds of Regular Graphs with Small Cliques
<p>The chromatic threshold of a class of graphs is the value <em>θ</em> such that any graph in this class with a minimum degree greater than <em>θn</em> has a bounded chromatic number. Several important results related to the chromatic threshold of triangle-free graphs have been reached in the last …
-
Sparse Recovery: Fundamental Limits, Measurement Constructions And Graph Constraints
… matrices are Gaussian, we provide sharp thresholds of the sparsity ratio (percentage of nonzero entries of a vector) that differentiates the success and failure of sparse recovery. We consider its strong recovery performance which requires to recover all the sparse vectors up to certain …