A minimal covering of a graph G with isomorphic copies of graph H is a set {H1, H2, H3, ... , Hn} where Hi is isomorphic to H, the vertex set of Hi is a subset of G, the edge set of G is a subset of the union of Hi's, and the cardinality of the union of Hi's minus G is minimum. Some studies have been made of covering the complete graph in which case an added condition of the edge set of Hi is the subset of the edge set of G for all i which implies no additional restrictions. However, if G is not the complete graph, then this condition may have implications. We will give necessary and sufficient conditions for minimal coverings of complete bipartite graph with 6-cycles, which we call minimal unrestricted coverings. We also give necessary and sufficient conditions for minimal coverings of the complete bipartite graph with 6-cycles with the added condition the edge set of Hi is a subset of G for all i, and call these minimal restricted coverings.

In this thesis, we consider packings and coverings of various complete graphs with the 4-cycle with a pendant edge. We consider both restricted and unrestricted coverings. Necessary and sufficient conditions are given for such structures for (1) complete graphs Kv, (2) complete bipartite graphs Km,n, and (3) complete graphs with a hole K(v,w).

In this thesis, we study universal hypergraphs. What are these? Let us start with defining a universal graph as a graph on n vertices that contains each of the many possible graphs of a smaller size k < n as an induced subgraph. A hypergraph is a discrete structure on n vertices in which edges can be of any size, unlike graphs, where the edge size is always two. If all edges are of size three, then the hypergraph is said to be 3-uniform. If a 3-uniform hypergraph can have edges colored one of a colors, then it is called a 3-uniform hypergraph with a colors. Analogously with universal graphs, a universal, induced, 3-uniform, k-hypergraph, with a possible edge colors is then defined to be a 3-uniform a-colored hypergraph on n vertices that contains each of the many possible 3-uniform a-colored hypergraphs on k vertices, k < n. In this thesis, we study conditions for the existence of a such a universal hypergraph, and address the question of how large n must be, given a fixed k, so that hypergraphs on n vertices are universal with high probability. This extends the work of Alon, [2] who studied the case of a = 2, and that too for graphs (not hypergraphs).

In this thesis we will study conditions for the existence of minimal sized omnipatterns in higher dimensions. We will introduce recent work conducted on one dimensional and two dimensional patterns known as omnisequences and omnimosaics, respectively. These have been studied by Abraham et al [3] and Banks et al [2]. The three dimensional patterns we study are called omnisculptures, and will be the focus of this thesis. A (K,a) omnisequence of length n is a string of letters that contains each of the ak words of length k over [A]={1,2,...a} as a substring. An omnimosaic O(n,k,a) is an n × n matrix, with entries from the set A ={1,2,...,a}, that contains each of the {ak2} k × k matrices over A as a submatrix. An omnisculpture is an n × n × n sculpture (a three dimensional matrix) with entries from set A ={1,2,...,a} that contains all the ak3 k × k × k subsculptures as an embedded submatrix of the larger sculpture. We will show that for given k, the existence of a minimal omnisculpture is guaranteed when kak2/3/e ≤ n ≤kak2/3/e(1+ε) and ε=εk → 0 is a sufficiently small function of k.

As introduced by Slater in 2008, liar's domination provides a way of modeling protection devices where one may be faulty. Assume each vertex of a graph G is the possible location for an intruder such as a thief. A protection device at a vertex v is assumed to be able to detect the intruder at any vertex in its closed neighborhood N[v] and identify at which vertex in N[v] the intruder is located. A dominating set is required to identify any intruder's location in the graph G, and if any one device can fail to detect the intruder, then a double-dominating set is necessary. Stronger still, a liar's dominating set can identify an intruder's location even when any one device in the neighborhood of the intruder vertex can lie, that is, any one device in the neighborhood of the intruder vertex can misidentify any vertex in its closed neighborhood as the intruder location or fail to report an intruder in its closed neighborhood. In this thesis, we present the liar's domination number for the finite ladders, infinite ladder, and infinite P_3 x P_infty. We also give bounds for other grid graphs.

Most results on pattern containment deal more directly with pattern avoidance, or the enumeration and characterization of strings which avoid a given set of patterns. Little research has been conducted regarding the word size required for a word to contain all patterns of a given set of patterns. The set of patterns for which containment is sought in this thesis is the set of preferential arrangements of a given length. The term preferential arrangement denotes strings of characters in which repeated characters are allowed, but not necessary. Cardinalities for sets of all preferential arrangements of given lengths and alphabet sizes are found, as well as cardinalities for sets where reversals fall into the same equivalence class and for sets in higher dimensions. The minimum word length and the word length necessary for a strict superpattern to contain all preferential arrangements for alphabet sizes two and three are also detailed.

A graph G is a (t, r)-regular graph if every collection of t independent vertices is collectively adjacent to exactly r vertices. If a graph G is (2, r)-regular where p, s, and m are positive integers, and m ≥ 2, then when n is sufficiently large, then G is isomorphic to G = Ks+mKp, where 2(p-1)+s = r. A nested (2,r)-regular graph is constructed by replacing selected cliques with a (2,r)-regular graph and joining the vertices of the peripheral cliques. For example, in a nested 's' graph when n = s + mp, we obtain n = s1+m1p1+mp. The nested 's' graph is now of the form Gs = Ks1+m1Kp1+mKp. We examine the network properties such as the average path length, clustering coefficient, and the spectrum of these nested graphs.

A set of vertices S in a graph G is a global dominating set (GDS) of G if S is a dominating set for both G and its complement G. The minimum cardinality of a global dominating set of G is the global domination number of G. We explore the effects of graph modifications on the global domination number. In particular, we explore edge removal, edge addition, and vertex removal.

A set S of vertices in a graph G = (V,E) is a dominating set if every vertex in V \ S is adjacent to at least one vertex in S. A vertex v in a dominating set S is said to be it cost effective if it is adjacent to at least as many vertices in V \ S as it is in S. A dominating set S is cost effective if every vertex in S is cost effective. The minimum cardinality of a cost effective dominating set of G is the cost effective domination number of G. In addition to some preliminary results for general graphs, we give lower and upper bounds on the cost effective domination number of trees in terms of their domination number and characterize the trees that achieve the upper bound. We show that every value of the cost effective domination number between these bounds is realizable.

A decomposition D of a graph H by a graph G is a partition of the edge set of H such that the subgraph induced by the edges in each part of the partition is isomorphic to G. A mixed graph on V vertices is an ordered pair (V,C), where V is a set of vertices, |V| = v, and C is a set of ordered and unordered pairs, denoted (x, y) and [x, y] respectively, of elements of V [8]. An ordered pair (x, y) ∈ C is called an arc of (V,C) and an unordered pair [x, y] ∈ C is called an edge of graph (V,C). A path on n vertices is denoted as Pn. A partial orientation on G is obtained by replacing each edge [x, y] ∈ E(G) with either (x, y), (y, x), or [x, y] in such a way that there are twice as many arcs as edges. The complete mixed graph on v vertices, denoted Mv, is the mixed graph (V,C) where for every pair of distinct vertices v1, v2 ∈ V , we have {(v1, v2), (v2, v1), [v1, v2]} ⊂ C. The goal of this thesis is to establish necessary and sufficient conditions for decomposition of Mv by all possible partial orientations of P4.