Topics in Information Dissemination, Network Fortification and Extremal Structures

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.

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.

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.

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.

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.

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