Topics in Information Dissemination, Network Fortification and Extremal Structures

<p>This thesis considers several problems in Combinatorial Optimization and Extremal Graph theory. In Combinatorial Optimization, the goal is to find efficient algorithms or near-optimal approximations of natural questions in networks. In Extremal Graph Theory, the objective is often determining the extremal graphs that maximizes/minimizes some specific subgraph while obeying certain local structural constraints.</p> <p>In Chapter 2, we propose and study a new model of disseminating information from a root called the Vector Clock Model. We provide several near-optimal approximation schedules that best distribute newly-formed information to all nodes in the graph.</p> <p>Chapter 3 contains interdiction problems where an attacker with a limited budget wish to destroy the edge-connectivity of a graph as much as possible. We introduce a generalization called Vertex Downgrading and provides bicriteria approximations for this provably-hard-to-approximate problem.</p> <p>The goal of the problems in Chapter 4 is to increase the weight of individual edges in a graph in order to maximize the increase of the weight of a Minimum Spanning Tree. We provide a constant approximation to a unit discrete model and provides a correction to a solution provided by Frederickson and Solis-Oba in [45] for the continuous model.</p> <p>In Chapter 5 and 6, we study generalized Tur´an problems where the obajective is to maximize the number of cliques of a certain size given the graph has a fixed number of vertices (or edges) and does not contain a specific subgraph (such as a star of a fixed size or paths/cycles of a certain length). We provide the complete characterization of the extremal graphs to these questions.</p> <p>Lastly, in Chapter 7, we investigate a bipartite saturation problem that was first studied over fifty years ago. We confirm a conjecture by Moshkovitz and Shapira for a special case, with the classification of the extremal graphs. We also improve the estimates of Gan, Kor´andi, and Sudakov for the general problem..</p>