No abstract uploaded!

In his article “Defend the Roman Empire!” (1999), Ian Stewart discussed a strategy of Emperor Constantine for defending the Roman Empire. Motivated by this article, Cockayne et al. (2004) introduced the notion of Roman domination in graphs. Let 𝐺 = (𝑉, 𝐸) be a graph. A Roman dominating function of 𝐺 is a function 𝑓 ∶ 𝑉 → {0, 1, 2} such that every vertex 𝑣 for which 𝑓(𝑣) = 0 has a neighbor 𝑢 with 𝑓(𝑢) = 2. The weight of a Roman dominating function 𝑓 is 𝑤(𝑓) =∑_𝑣∈𝑉 𝑓(𝑣). The Roman domination number of a graph 𝐺, denoted by 𝛾_𝑅(𝐺), is the minimum weight of all possible Roman dominating functions. This paper introduces a quantity 𝑅(𝑥𝑦) for each pair of non-adjacent vertices {𝑥, 𝑦 }in 𝐺, called the Roman dominating index of{ 𝑥, 𝑦} , which is defined by &𝑅(𝑥𝑦) = 𝛾_𝑅(𝐺) − 𝛾_𝑅(𝐺 + 𝑥𝑦)&. We prove that 0 ≤ 𝑅(𝑥𝑦) ≤ 1 and give a necessary and sufficient condition on {𝑥, 𝑦} for which 𝑅(𝑥𝑦)= 1. This paper also introduces the Roman-critical graph. We call 𝐺 = (𝑉, 𝐸) Roman-critical if 𝛾_𝑅(𝐺 − 𝑒) > 𝛾_𝑅(𝐺) , ∀𝑒 ∈ 𝐸 . It is proved that a Roman-critical graph can only be a star graph whose order is not equal to 2, or the union of such graphs. In addition, this paper shows that for each connected graph 𝐺 of order& 𝑛 ≥ 3,2 ≤ 𝛾_𝑅(𝐺) ≤frac{4𝑛}{5}&. A family of graphs for which the respective equality holds is also provided. Finally, this paper finds the lower bound of the Roman domination number for 3-regular graphs and the exact value of the Roman domination number for &𝐶_frac{𝑛}{2}*𝑃2& and 3-regular circulant graphs.

In Ramsey theory (a branch of combinatorics) one often proves that a function exists by giving enormous bounds on it. The function's actual values may be much smaller; however, this is not known. In this paper we explore variants and special cases of these functions where we obtain much smaller bounds. The following is known: no matter how the lattice points of a coordinate plane are colored red and blue, there exists a square whose corners are the same color (a monochromatic square). In fact, using more than just two colors will still guarantee a monochromatic square (one whose vertices are the same color). So for all c (the number of colors), there is a number G(c) where all colorings with c colors of the lattice points of a G(c)*G(c) grid will contain a monochromatic square. Unfortunately, the necessary number of points is unknown, but bounds are known. These bounds are enormous,however. So we look at a variant of this problem in order to work with more manageable bounds. Looking for rectangles or right triangles rather than squares makes these bounds polynomial. We explore which grids contain a specic number of rectangles or right triangles. It is known that if the naturals are colored with two colors, there will be two of the same color that are a square apart. Once again, this is true for any number of colors. It is also true for any polynomial whose constant term is 0 and for multiple polynomials. This is known as the Polynomial Van der Waerden Theorem, or PolyVDW. The bounds on the number of naturals that have to be colored grow very quickly. However, for quadratic polynomials and 2 or 3 colors, there are some cases where the theorem is false, and others where it is true with polynomial bounds. Since PolyVDW does not hold in its entirety for all such polynomials, we try to classify for which of these polynomials and for which numbers of colors the theorem holds and try to nd bounds for them. We explore monochromatic rectangles and right triangles rather than squares in order to get reasonable bounds on the grid sizes necessary to guarantee the existence of these monochromatic shapes. We also explore the necessary grid sizes for multiple rectangles and right triangles. In fact, we nd many exact numbers. In addition, we look at variants of PolyVDW and obtain much better upper bounds for these numbers than are known for the standard PolyVDW numbers.