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, and the minimum cardinality of a dominating set of G is the domination number of G. A vertex v in a dominating set S is said to be very cost effective if it is adjacent to more vertices in V\S than to vertices in S. A dominating set S is very cost effective if every vertex in S is very cost effective. The minimum cardinality of a very cost effective dominating set of G is the very cost effective domination number of G. We first give necessary conditions for a graph to have equal domination and very cost effective domination numbers. Then we determine an upper bound on the very cost effective domination number for trees in terms of their domination number, and characterize the trees which attain this bound. lastly, we show that no such bound exists for graphs in general, even when restricted to bipartite graphs.

In this paper, we consider decompositions of the complete graph on v vertices into 4-cycles with a pendant edge. In part, we will consider decompositions which admit automorphisms consisting of: (1) a single cycle of length v, (2) f fixed points and a cycle of length v − f, or (3) two disjoint cycles. The purpose of this thesis is to give necessary and sufficient conditions for the existence of cyclic, f-cyclic, and bicyclic Q-decompositions of Kv.

There are four orientations of cycles on four vertices. Necessary and sufficient conditions are given for covering complete directed digraphs Dv, packing and covering complete bipartite digraphs, Dm,n, and packing and covering the complete digraph on v vertices with hole of size w, D(v,w), with three of the orientations of a 4-cycle, including C4, X, and Y.

The alphabet overlap graph is a modification of the well known de Bruijn graph. De Bruijn graphs have been highly studied and hence many properties of these graphs have been determined. However, very little is known about alphabet overlap graphs. In this work we determine the chromatic number for a special case of these graphs. We define the alphabet overlap graph by G = AO(a, k, t, where a, k and t are positive integers such that 0 ≤ t ≤ k. The vertex set of G is the set of all k-letter sequences over an alphabet of size a. Also there is an edge between vertices u, v if and only if the last t letters in u match the first t letters in v or the first t letters in u match the last t letters in v. We consider the chromatic number for the AO(a, k, t graphs when k > 2, t = k - 1 and a = 2.

For a graph G=(V,E) and a set of vertices S, a vertex v in S is said to be very cost effective if it is adjacent to more vertices in V -S than in S. A bipartition pi={S, V- S} is called very cost effective if both S and V- S are very cost effective sets. Not all graphs have a very cost effective bipartition, for example, the complete graphs of odd order do not. We consider several families of graphs G, including Cartesian products and cacti graphs, to determine whether G has a very cost effective bipartition.

For a graph G=(V,E), a set S⊆V is a global supply set if every vertex v∈V\S has at least one neighbor, say u, in S such that u has at least as many neighbors in S as v has in V \S. The global supply number is the minimum cardinality of a global supply set, denoted γgs (G). We introduce global supply sets and determine the global supply number for selected families of graphs. Also, we give bounds on the global supply number for general graphs, trees, and grid graphs.

This thesis explores functionally Alexandroff topologies and the order theory asso- ciated when considering the collection of such topologies on some set X. We present several theorems about the properties of these topologies as well as their partially ordered set. The first chapter introduces functionally Alexandroff topologies and motivates why this work is of interest to topologists. This chapter explains the historical context of this relatively new type of topology and how this work relates to previous work in topology. Chapter 2 presents several theorems describing properties of functionally Alexandroff topologies ad presents a characterization for the functionally Alexandroff topologies on a finite set X. The third and fourth chapters present facts about the lattice of functionally Alexandroff topologies, with Chapter 4 being dedicated to an algorithm which generates a complement in this lattice.

In this paper we explore generalized “$r$-Fibonacci Numbers” using a combinatorial “tiling” interpretation. This approach allows us to provide simple, intuitive proofs to several identities involving $r$-Fibonacci Numbers presented by F.T. Howard and Curtis Cooper in the August, 2011, issue of the Fibonacci Quarterly. We also explore a connection between the generalized Fibonacci numbers and a generalized form of binomial coefficients.

We examine the problem of counting interval graphs. We answer the question posed by Hanlon, of whether the formal power series generating function of the number of interval graphs on n vertices has a positive radius of convergence. We have found that it is zero. We have obtained a lower bound and an upper bound on the number of interval graphs on n vertices. We also study the application of interval graphs to the dynamic storage allocation problem. Dynamic storage allocation has been shown to be NP-complete by Stockmeyer. Coloring interval graphs on-line has applications to dynamic storage allocation. The most colors used by Kierstead's algorithm is 3 ω -2, where ω is the size of the largest clique in the graph. We determine a lower bound on the colors used. One such lower bound is 2 ω -1.

In 1946, Erdös posed the distinct distances problem, which asks for the minimum number of distinct distances that any set of n points in the real plane must realize. Erdös showed that any point set must realize at least &Omega(n1/2) distances, but could only provide a construction which offered &Omega(n/&radic(log(n)))$ distances. He conjectured that the actual minimum number of distances was &Omega(n1-&epsilon) for any &epsilon > 0, but that sublinear constructions were possible. This lower bound has been improved over the years, but Erdös' conjecture seemed to hold until in 2010 Larry Guth and Nets Hawk Katz used an incidence theory approach to show any point set must realize at least &Omega(n/log(n)) distances. In this thesis we will explore how incidence theory played a roll in this process and expand upon recent work by Adam Sheffer and Cosmin Pohoata, using geometric incidences to achieve bounds on the bipartite variant of this problem. A consequence of our extensions on their work is that the theoretical upper bound on the original distinct distances problem of &Omega(n/&radic(log(n))) holds for any point set which is structured such that half of the n points lies on an algebraic curve of arbitrary degree.