An Italian dominating function on a graph $G = (V,E)$ is a function such that $f : V \to \{0,1,2\}$, and for each vertex $v \in V$ for which $f(v) = 0$, we have $\sum_{u\in N(v)}f(u) \geq 2$. The weight of an Italian dominating function is $f(V) = \sum_{v\in V(G)}f(v)$. The minimum weight of all such functions on a graph $G$ is called the Italian domination number of $G$. In this thesis, we will consider Italian domination in various types of products of a graph $G$ with the complete graph $K_2$. We will find the value of the Italian domination number for ladders, specific families of prisms, mobius ladders and related products including categorical products $G\times K_2$ and lexicographic products $G\cdot K_2$. Finally, we will conclude with open problems.

See supplemental content for abstract

In this paper, new variations of some well-known permutation statistics are introduced and studied. Firstly, a double-descent of a permutation π is defined as a position i where πi ≥ 2πi+1. By proofs by induction and direct proofs, recursive and explicit expressions for the number of n-permutations with k double-descents are presented. Also, an expression for the total number of double-descents in all n-permutations is presented. Secondly, a double-inversion of a permutation π is defined as a pair (πi,πj) where i<j but πi ≥ 2πj. The total number of double-inversions in all n-permutations is presented.

In 2004 Alexander Postnikov and Boris Shapiro introduced a class of commutative algebras for non-directed graphs. There are two main types of such algebras, algebras of the first type count spanning trees and algebras  of the second type count spanning forests. These algebras have a number of interesting properties including an explicit formula for their Hilbert series. In this thesis we mainly work with the second type of algebras, we discover more properties of the original algebra and construct a few generalizations. In particular we prove that the algebra counting forests depends only on graphical matroid of the graph and converse. Furthermore, its "K-theoretic" filtration reconstructs the whole graph. We introduse $t$ labelled algebras of a graph, their Hilbert series contains complete information about the Tutte polynomial of the initial graph. Finally we introduce similar algebras for hypergraphs. To do this, we define spanning forests and trees of a hypergraph and the corresponding "hypergraphical" matroid.

In this thesis, we introduce Roman domination cover rubbling as an extension of domination cover rubbling. We define a parameter on a graph $G$ called the \textit{Roman domination cover rubbling number}, denoted $\rho_{R}(G)$, as the smallest number of pebbles, so that from any initial configuration of those pebbles on $G$, it is possible to obtain a configuration which is Roman dominating after some sequence of pebbling and rubbling moves. We begin by characterizing graphs $G$ having small $\rho_{R}(G)$ value. Among other things, we also obtain the Roman domination cover rubbling number for paths and give an upper bound for the Roman domination cover rubbling number of a tree.

This study is an investigation of the performance of a discrete latent state model devised by Paulson (1982) to account for signed-number arithmetic test data gathered by Birenbaum and Tatsuoka (1980). One hundred twenty nine students took a test which consists of sixteen item types with four parallel arithmetic items of each type. The present study utilizes the five addition item types of four items each; hence, there are four parallel subtests. Responses to the addition items can be analyzed in terms of two components: the siqn component (is the sign correct?), and the absolute value component (is the size of the answer correct?). Paulson's model describes how students perform on the two components separately and how the component responses are related. This study examines the parallelism of the four subtests, in terms of equality of means, standard deviations, and correlations between all pairs of subtests. Decision consistency between subtests is another useful indicator of measurement reliability, particularly for tests of concept mastery. The model implies that the consistency between any two pairs of subtests should be equal; this implication is tested. The specific numerical values predicted by the model for the means, standard deviations, correlations, and decision consistency indices are tested against the corresponding observed statistics. All the analyses described so far are done separately for both the sign and the absolute value components of the responses. A method to synthesize overall correct response from estimated parameter values of two components is derived and tested against observed values. The results are that "parallel" items within item types are not all parallel and finer characterization would be needed to describe the items completely. However, the deviations from strict parallelism are slight. Paulson's model demonstrates good predictive ability; on both components and on the overall responses. Most of the deviations from the prediction can be attributed to not strictly parallel subtests and estimated parameter values not being the best possible estimates.

The set PLS(a, b; n) is the set of all partial latin squares of order n with a completed rows, b completed columns and all other cells empty. We identify reductions of partial latin squares in PLS(2, 3; n) by using permutations described by filled rows and intersections of filled rows and columns. We find that all partial latin squares in PLS(2, 3;n), where n is sufficiently large, can be completed if such a reduction can be completed. We also show that all partial latin squares in PLS(2, 3; n) where the intersection of filled rows and columns form a latin rectangle have completions for n ≥ 8.

Let S ⊆ V be an arbitrary subset of vertices of a graph G = (V,E). The differential ∂(S) equals the difference between the cardinality of the set of vertices not in S but adjacent to vertices in S, and the cardinality of the set S. The differential of a graph G equals the maximum differential of any subset S of V . A set S is called a zero set if ∂(S) = 0. In this thesis we introduce the study of zero sets in graphs. We give proofs of the existence of zero sets in various kinds of graphs such as even order graphs, bipartite graphs, and graphs of maximum degree 3. We also give proofs regarding the existence of graphs which contain no zero sets and the construction of zero-free graphs from graphs which contain zero sets.

The Internet of Things (IoT) is an important and expanding technology used for a large variety of applications to monitor and automate processes. The aim of this thesis is to present a way to find and assign locally unique IDs to access points (APs) in enormous wireless IoT systems where mobile tags are traversing the network and communicating with multiple APs simultaneously. This is done in order to improve the robustness of the system and increase the battery time of the tags. The resulting algorithm is based on transforming the problem into a graph coloring problem and solving it using approximate methods. Two metaheuristics: Simulated annealing and tabu search were implemented and compared for this purpose. Both of these showed similar results and neither was clearly superior to the other. Furthermore, the presented algorithm can also exclude nodes from the coloring based on the results in order to ensure a proper solution that also satisfies a robustness criterion. A metric was also created in order for a user to intuitively evaluate the quality of a given solution. The algorithm was tested and evaluated on a system of 222 APs for which it produced good results.

The core idea of Ramsey theory is that complete disorder is impossible. Given a large structure, no matter how complex it is, we can always find a smaller substructure that has some sort of order. One view of this problem is in edge-colorings of complete graphs. For any graphs G, H1, ..., Hk, we write G → (H1, ..., Hk), or G → (H)k when H1 = ··· = Hk = H, if every k-edge-coloring of G contains a monochromatic Hi in color i for some i ∈ {1,...,k}. The Ramsey number rk(H1, ..., Hk) is the minimum integer n such that Kn → (H1, ..., Hk), where Kn is the complete graph on n vertices. Computing rk(H1, ..., Hk) is a notoriously difficult problem in combinatorics. A weakening of this problem is to restrict ourselves to Gallai colorings, that is, edge-colorings with no rainbow triangles. From this we define the Gallai-Ramsey number grk(K3,G) as the minimum integer n such that either Kn contains a rainbow triangle, or Kn → (G)k . In this thesis, we determine the Gallai-Ramsey numbers for C7 with multiple colors. We believe the method we developed can be applied to find grk(K3, C2n+1) for any integer n ≥ 2, where C2n+1 denotes a cycle on 2n + 1 vertices.