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.

Let G = (V (G), E(G)) be a graph and G̅ be the complement of G. The complementary prism of G, denoted GG̅, is the graph formed from the disjoint union of G and G̅ by adding the edges of a perfect matching between the corresponding vertices of G and G̅. A set D ⊆ V (G) is a locating-dominating set of G if for every u ∈ V (G)D, its neighborhood N(u)⋂D is nonempty and distinct from N(v)⋂D for all v ∈ V (G)D where v ≠ u. The locating-domination number of G is the minimum cardinality of a locating-dominating set of G. In this thesis, we study the locating-domination number of complementary prisms. We determine the locating-domination number of GG̅ for specific graphs and characterize the complementary prisms with small locating-domination numbers. We also present bounds on the locating-domination numbers of complementary prisms.

Let G be a graph and G̅ be the complement of G. The complementary prism GG̅ of G is the graph formed from the disjoint union of G and G̅ by adding the edges of a perfect matching between the corresponding vertices of G and G̅. For example, if G is a 5-cycle, then GG̅ is the Petersen graph. In this paper we investigate independent domination in complementary prisms.

In this thesis, we consider the decomposition of the complete mixed graph on v vertices denoted Mv, into every possible mixed graph on three vertices which has (like Mv) twice as many arcs as edges. Direct constructions are given in most cases. Decompositions of theλ-fold complete mixed graph λMv, are also studied.

Let G be a graph. For k ≥ d ≥ 1, a k/d -coloring of G is a coloring c of vertices of G with colors 0, 1, 2, . . ., k - 1, such that d ≤ | c(x) - c(y) | ≤ k - d, whenever xy is an edge of G. We say that the circular chromatic number of G, denoted χc(G), is equal to the smallest k/d where a k/d -coloring exists. In [6], Pan and Zhu have given a function μ(g) that gives an upper bound for the circular-chromatic number for every K4-minor-free graph Gg of odd girth at least g, g ≥ 3. In [7], they have shown that their upper bound in [6] can not be improved by constructing a sequence of graphs approaching μ(g) asymptotically. We prove that for every odd integer g = 2k + 1, there exists a graph Gg ∈ G/K4 of odd girth g such that χc(Gg) = μ(g) if and only if k is not divisible by 3. In other words, for any odd g, the question of attainability of μ(g) is answered for all g by our results. Furthermore, the proofs [6] and [7] are long and tedious. We give simpler proofs for both of their results.