Voltage graph theory can be used to describe embeddings of product graphs if one factor is a Cayley graph. We use voltage graphs to explore embeddings of various products where one factor is a hypercube, describing some minimal and symmetrical embeddings. We then define a graph product, the weak symmetric difference, and illustrate a voltage graph construction useful for obtaining an embedding of the weak symmetric difference of an arbitrary graph with a hypercube.

Let G = (V, E) be a graph and let S ⊆ V be a subset of vertices. The set S is a defensive alliance if for all x ∈ S, |N[x] ∩ S| ≥ |N[x] − S|. The concept of defensive alliances was introduced in [KHH04], primarily for the modeling of nations in times of war, where allied nations are in mutual agreement to join forces if any one of them is attacked. For a vertex x in a defensive alliance, the number of neighbors of x inside the alliance, plus the vertex x, is at least the number of neighbors of x outside the alliance. In a graph model, the vertices of a graph represent nations and the edges represent country boundaries. Thus, if the nation corresponding to a vertex x is attacked by its neighbors outside the alliance, the attack can be thwarted by x with the assistance of its neighbors in the alliance. In a different subject matter, [FLG00] applies graph theory to model the world wide web, where vertices represent websites and edges represent links between websites. A web community is a subset of vertices of the web graph, such that every vertex in the community has at least as many neighbors in the set as it has outside. So, a web community C satisfies ∀x ∈ C, |N[x] ∩ C| > |N[x] − C|. These sets are very similar to defensive alliances. They are known as strong defensive alliances in the literature of alliances in graphs. Other areas of application for alliances and related topics include classification, data clustering, ecology, business and social networks. iii Consider the application of modeling nations in times of war introduced in the first paragraph. In a defensive alliance, any attack on a single member of the alliance can be successfully defended. However, as will be demonstrated in Chapter 1, a defensive alliance may not be able to properly defend itself when multiple members are under attack at the same time. The concept of secure sets is introduced in [BDH07] for exactly this purpose. The non-empty set S is a secure set if every subset X ⊆ S, with the assistance of vertices in S, can successfully defend against simultaneous attacks coming from vertices outside of S. The exact definition of simultaneous attacks and how such attacks may be defended will be provided in Chapter 1. In [BDH07], the authors presented an interesting characterization for secure sets which resembles the definition of defensive alliances. A non-empty set S is a secure set if and only if ∀X ⊆ S, |N[X] ∩ S| ≥ |N[X] − S| ([BDH07], Theorem 11). The cardinality of a minimum secure set is the security number of G, denoted s(G). A secure set S is a global secure set if it further satisfies N[S] = V . The cardinality of a minimum global secure set of G is the global security number of G, denoted γs(G). In this work, we present results on secure sets and global secure sets. In particular, we treat the computational complexity of finding the security number of a graph, present algorithms and bounds for the global security numbers of trees, and present the exact values of the global security numbers of paths, cycles and their Cartesian products.

There has been much recent interest in random graphs sampled uniformly from the set of (labelled) graphs on n vertices in a suitably structured class A. An important and well-studied example of such a suitable structure is bridge-addability, introduced in 2005 by McDiarmid et al. in the course of studying random planar graphs. A class A is bridge-addable when the following holds: if we take any graph G in A and any pair u,v of vertices that are in different components in G, then the graph G′ obtained by adding the edge uv to G is also in A. It was shown that for a random graph sampled from a bridge-addable class, the probability that it is connected is always bounded away from 0, and the number of components is bounded above by a Poisson law. What happens if ’bridge-addable’ is replaced by something weaker? In this thesis, this question is explored in several different directions. After an introductory chapter and a chapter on generating function methods presenting standard techniques as well as some new technical results needed later, we look at minor-closed, labelled classes of graphs. The excluded minors are always assumed to be connected, which is equivalent to the class A being decomposable - a graph is in A if and only if every component of the graph is in A. When A is minor-closed, decomposable and bridge-addable various properties are known (McDiarmid 2010), generalizing results for planar graphs. A minor-closed class is decomposable and bridge-addable if and only if all excluded minors are 2-connected. Chapter 3 presents a series of examples where the excluded minors are not 2-connected, analysed using generating functions as well as techniques from graph theory. This is a step towards a classification of connectivity behaviour for minor-closed classes of graphs. In contrast to the bridge-addable case, different types of behaviours are observed. Chapter 4 deals with a new, more general vari- ant of bridge-addability related to edge-expander graphs. We will see that as long as we are allowed to introduce ’sufficiently many’ edges between components, the number of components of a random graph can still be bounded above by a Pois- son law. In this context, random forests in Kn,n are studied in detail. Chapter 5 takes a different approach, and studies the class of labelled forests where some vertices belong to a specified stable set. A weighting parameter y for the vertices belonging to the stable set is introduced, and a graph is sampled with probability proportional to y*s where s is the size of its stable set. The behaviour of this class is studied for y tending to ∞. Chapters 6 concerns random graphs sampled from general decomposable classes. We investigate the minimum size of a component, in both the labelled and the unlabelled case.

Synchronization is an important phenomenon which plays a central role in the function or dysfunction of a wide spectrum of biological and technological networks. Despite the vast literature on network synchronization, the majority of research activities have been focused on oscillators connected through one network. However, in many realistic biological and engineering systems the units can be coupled via multiple, independent networks. This thesis contributes toward the rigorous understanding of the emergence of stable synchronization in dynamical networks with mixed coupling. A mixed network is composed of subgraphs connecting a subnetwork of oscillators via one of the individual oscillator's variables. An illustrative example is a network of Lorenz systems with mixed couplings where some of the oscillators are coupled through the x-variable, some through the y-variable and some through both. This thesis presents a new general synchronization method called the Mixed Connection Graph method, which removes a long-standing obstacle in studying synchronization in mixed dynamical networks of different nature. This method links the stability theory, including the Lyapunov function approach with graph theoretical quantities. The application of the method to specific networks reveals surprising, counterintuitive effects, not seen in networks with one connection graph.

published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

No description available.

Recent advances in linear programming solution methodology have focused on interior point algorithms. These are powerful new methods, achieving significant reductions in computer time for large LPs and solving problems significantly larger than previously possible. This dissertation describes the implementation of interior point algorithms. It focuses on applications of direct sparse matrix methods to sparse symmetric positive definite systems of linear equations on scalar computers and vector supercomputers. The most computationally intensive step in each iteration of any interior point algorithm is the numerical factorization of a sparse symmetric positive definite matrix. In large problems or relatively dense problems, 80-90% or more of computational time is spent in this step. This study concentrates on solution methods for such linear systems. It is based on modifications and extensions of graph theory applied to sparse matrices. The row and column permutation of a sparse symmetric positive definite matrix dramatically affects the performance of solution algorithms. Various reordering methods are considered to find the best ordering for various numerical factorization methods and computer architectures. It is assumed that the reordering method will follow the fill-preserving rule, i.e., not allow additional fill-ins beyond that provided by the initial ordering. To follow this rule, a modular approach is used. In this approach, the matrix is first permuted by using any minimum degree heuristic, and then the permuted matrix is again reordered according to a specific reordering objective. Results of different reordering methods are described. There are several ways to compute the Cholesky factor of a symmetric positive definite matrix. A column Cholesky algorithm is a popular method for dense and sparse matrix factorization on serial and parallel computers. Applying this algorithm to a sparse matrix requires the use of sparse vector operations. Graph theory is applied to reduce sparse vector computations. A second and relatively new algorithm is the multifrontal algorithm. This method uses dense operations for sparse matrix computation at the expense of some data manipulation. The performance of the column Cholesky and multifrontal algorithms in the numerical factorization of a sparse symmetric positive definite matrix on an IBM 3090 vector supercomputer is described.

Center location on cactus graphs. The p-center problem has been shown to be NP-hard for case of a general graph, yet polynomial algorithms exist for the case of a tree graph. Specifically, we consider "cactus graphs" where each edge is contained in at most one cycle. We show that the p-center problem on this class can be solved in polynomial time using a decomposition algorithm. We partition the graph into a set of subgraphs which are then solved sequentially. The solutions to the subgraphs are linked by a single parameter. The algorithm runs in polynomial time. Locating capacity limited centers on trees. The uncapacitated p-center problem on trees is solvable in polynomial time. We extend this result to include the case where each center can serve a limited number of customers and show that the capacitated p-center on trees can be solved in polynomial time when the capacities are identical. The algorithm consists of solving a capacitated covering problem and then using search routines to find the optimal domination radius. Center location on spheres. We discuss the unweighted center location problem. The following results are presented: (i) An O(n) time algorithm to solve the 1-center problem if the vertices are on one half of the sphere, and an O(n) time algorithm to check whether this condition holds. Both algorithms are based on presenting the problems as 3-dimensional convex programming problems with linear constraints and applying a pruning technique to find the optimum in O(n) time. (ii) An O(n$\sp3$ log n) time algorithm for the 2-center problem on the whole sphere. (iii) A reduction to show that the general p-center problem on a sphere is NP-hard. Locating hyperplanes on hypercubes. In linear regression models we are interested in locating a (d-1) dimensional hyperplane that will be as "close" as possible to existing vertices in the d-dimensional hypercube. The least squares criterion is usually applied for the linear fitting problem; while fitting according to the least absolute value ("minisum") seems to be "complicated". We solve fitting problems with the minisum criterion and present linear time algorithms when the dimension d is fixed. (Abstract shortened with permission of author.)

The study of self-duality has attracted some attention over the past decade. A good deal of research in that time has been done on constructing and classifying all self-dual graphs and in particular polyhedra. We will give an overview of the recent research in the first two chapters. In the third chapter, we will show the necessary condition that a self-complementary self-dual graph have <i>n</i> &#8801; 0, 1 (mod 8) vertices and we will review White's infinite class (the Paley graphs, for which <i>n</i> &#8801; 1 (mod 8)). Finally, we will construct a new infinite class of self-complementary self-dual graphs for which <i>n</i> &#8801; 0 (mod 8).

This thesis will address several problems in discrete optimization. These problems are considered hard to solve. However, good approximation algorithms for these problems may be helpful in approximating problems in computational biology and computer science. Given an undirected graph G=(V,E) and a family of subsets of vertices S, the minimum crossing spanning tree is a spanning tree where the maximum number of edges crossing any single set in S is minimized, where an edge crosses a set if it has exactly one endpoint in the set. This thesis will present two algorithms for special cases of minimum crossing spanning trees. The first algorithm is for the case where the sets of S are pairwise disjoint. It gives a spanning tree with the maximum crossing of a set being 2OPT+2, where OPT is the maximum crossing for a minimum crossing spanning tree. The second algorithm is for the case where the sets of S form a laminar family. Let b_i be a bound for each S_i in S. If there exists a spanning tree where each set S_i is crossed at most b_i times, the algorithm finds a spanning tree where each set S_i is crossed O(b_i log n) times. From this algorithm, one can get a spanning tree with maximum crossing O(OPT log n). Given an undirected graph G=(V,E), and a family of subsets of vertices S, the minimum crossing perfect matching is a perfect matching where the maximum number of edges crossing any set in S is minimized. A proof will be presented showing that finding a minimum crossing perfect matching is NP-hard, even when the graph is bipartite and the sets of S are pairwise disjoint.