A Magic Venn Diagram is a magic figure where regions of a Venn diagram are labeled such that the sums of the regional labels of each set are the same. We have developed a backtracking search to count the number of Magic Venn Diagrams. The algorithm could determine the number of Magic Venn Diagrams for all Venn diagrams with four sets. This paper presents the algorithm with its applied heuristics and lists the computational results.

A famous open problem in the field of rendezvous search is to ascertain the rendezvous value of the symmetric rendezvous problem on the line, wherein both agents begin two units apart. We provide a new, Bayesian framework to both create new strategies for the agents to follow and to provide a new interpretation of previously posited strategies.
Additionally, we have developed a method that modifies any strategy, even those with potentially infinite expected meeting time, into a new strategy that is guaranteed to have a finite expected meeting time. This process, combined with using our Bayesian framework to create new strategies, yields an upper bound that is within one percent of the current best upper bound for the symmetric rendezvous value.

The Astronaut Problem is an open problem in the field of rendezvous search. The premise is that two astronauts randomly land on a planet and want to find one another. Research explores what strategies accomplish this in the least expected time.
To investigate this problem, we create a discrete model which takes place on the edges of the Platonic solids. Some baseline assumptions of the model are:

1. The agents can see all of the faces around them.
2. The agents travel along the edges from vertex to vertex and cannot jump.
3. The agents move at a rate of one edge length per unit time.

The 3-dimensional nature of our model makes it different from previous work. We explore multi-step strategies, which are strategies where both agents move randomly for one step, and then follow a pre-determined sequence.

For the cube and octahedron, we are able to prove optimality of the “Left Strategy,” in which the agents move in a random direction for the first step and then turn left. In an effort to find lower expected times, we explore mixed strategies. Mixed strategies incorporate an asymmetric case which, under certain conditions, can result in lower expected times.

Most of the calculations were done using first-step decompositions for Markov chains.

Our research focuses on the winning probability of a novel problem posted on a question-and-answer website. There are $n$ people in a line at positions $1,2,\dots ,n$. For each round, we randomly select a person at position $i$, where $i$ is odd, to leave the line, and shift each person at a position $j$ such that $j>i$ to position $j–1$. We continue to select people until there is only one person left, who then becomes the winner.

We are interested in which initial position has the greatest chance to survive, that is, the highest probability to be the last one remaining. Specifically, we have derived recursions to solve for exact values and the formula of the winning probabilities.

We have also considered variations of the problem, where people are grouped into triples, quadruples, etc., and the first person in each group is at the risk of being selected. We will also present various sequences we have discovered while solving for the winning probabilities of the different variations, as well as other possible extensions and related findings concerning this problem.

Our research studies the expected survival time in a novel problem posted on a question-and-answer website. There are $n$ people in a line at positions $1,2,\dots ,n$. For each round, we randomly select a person at position $k$, where $k$ is odd, to leave the line, and shift the person at each position $i>k$ to position $i-1$. We continue to select people until there is only one person left, who then becomes the winner.

We are interested in which initial position has the largest expected number of turns to stay in the line before being selected, which we refer to as “expected survival time.” In this paper, we use a recursive approach to solve for exact values of the expected survival time. We have proved the exact formula of the expected survival time of the first and the last position as well. We will also present our work on the expected survival time of the other positions, $2,3,4,\dots$ from an asymptotic perspective.

A set $S\subseteq V$ is a dominating set of $G$ if every vertex in $V–S$ is adjacent to at least one vertex in $S$. The domination number $\gamma (G)$ of $G$ equals the minimum cardinality of a dominating set $S$ in $G$; we say that such a set $S$ is a $\gamma$-set.

A generalization of this is partial domination, which was introduced in 2017 by Case, Hedetniemi, Laskar, and Lipman. In \emph{partial domination}, a set $S$ is a $p$-dominating set if it dominates a proportion $p$ of the vertices in $V$. The $p$-domination number ${\gamma }_p(G)$ is the minimum cardinality of a $p$-dominating set in $G$.

In this paper, we investigate further properties of partial dominating sets, particularly ones related to graph products and locating partial dominating sets. We also introduce the concept of a $p$-influencing set as the union of all $p$-dominating sets for a fixed $p$ and investigate some of its properties.

For bipartite graphs $F$ and $H$ and a positive integer $s$, the $s$-bipartite Ramsey number $B{R}_s(F,H)$ of $F$ and $H$ is the smallest integer $t$ with $t\ge s$ such that every red-blue coloring of $K_{s,t}$ results in a red $F$ or a blue $H$. We evaluate this number for all positive integers $s$ when $F$ and $H$ are both stars, are both matchings, or one is a star and the other is a matching, as well as when $F=H$ is an arbitrary double star.

In a graph $G$, the Steiner distance $d(S)$ of the vertex subset $S\subseteq V(G)$ is the minimum size among all connected subgraphs whose vertex sets contain $S$. The Steiner $k$-diameter of a connected graph $G$ is the maximum $d(S)$ among all $k$-element vertex subsets $S\subseteq V(G)$.

In this paper, we examine the Steiner $k$-diameter for large $k$ and then discuss the applications of the results.

A set of vertices, $S$, in a digraph $D$, is split dominating provided it is:

1. dominating and
2. $D[V(D)\setminus S]$ is either trivial or has a lower level of connection than $D$.

In this paper, we consider split dominating sets in strongly connected tournaments. The split domination number of a strongly connected tournament $T$, denoted by ${\gamma }_s(T)$, is the minimum cardinality of a split dominating set for that tournament.

The authors previously gave a tight lower bound for ${\gamma }_s(T)$ when $T$ is regular. In this paper, we show that when $T$ is a nearly regular $2k$-tournament, then ${\gamma }_s(T)\ge \lceil \frac{2k}{3}\rceil$ and this bound is tight.

Redrawing lines for redistricting plans that represent U.S. congressional districts is a tricky business. There are many laws that dictate how lines can and cannot be drawn, such as contiguity. In fact, building all redistricting plans for a single U.S. state is an intractable problem. Researchers have turned to heuristics in order to analyze current redistricting plans. Many of these heuristics (e.g. local search heuristics and Markov chain Monte Carlo algorithms) used by researchers form new congressional districts by switching the smaller pieces (e.g. precincts or census blocks) that make up congressional districts from one congressional district to another.
In this paper, we discuss the various natural definitions involved in satisfying rules for contiguity and simply connectedness of precincts or census blocks and how these relate to contiguity and simply connectedness of congressional districts. We also propose and analyze several constructions to alleviate violations of contiguity and simply connectedness in precincts and census blocks. Finally, we develop efficient algorithms that allow practitioners to assess redistricting plans using local search heuristics or Markov chain Monte Carlo algorithms efficiently.

A set $S\subseteq V$ is $\alpha$-dominating if for all $v\in V–S$, $|N(v)\cap S|\ge \alpha |N(v)|$. The $\alpha$-domination number of $G$ equals the minimum cardinality of an $\alpha$-dominating set $S$ in $G$. Since being introduced by Dunbar et al. in 2000, $\alpha$-domination has been studied for various graphs and a variety of bounds have been developed.

In this paper, we propose a new parameter derived by flipping the inequality in the definition of $\alpha$-domination. We say a set $S\subset V$ is a $\beta$-packing set of a graph $G$ if $S$ is a proper, maximal set having the property that for all vertices $v\in V–S$, $|N(v)\cap S|\le \beta |N(v)|$ for some $0<\beta \le 1$. The $\beta$-\emph{packing number} of $G$, denoted $\beta \text{-pack}(G)$, equals the maximum cardinality of a $\beta$-packing set in $G$.

In this research, we determine $\beta \text{-pack}(G)$ for several classes of graphs, and we explore some properties of $\beta$-packing sets.

A perfect matching of a graph is a subset of edges in the graph such that each vertex is contained in exactly one edge. We study the number of perfect matchings of a given graph. In particular, we are interested in the power of two that divides this number. A new type of vertex set, called a channel, is considered, whose presence is associated with powers of two in the perfect matching count. This provides a method for determining lower bounds on such powers. Algebraic and involutive proofs are given for these results, and methods for channel identification are provided. We specialize to perfect matchings on subgraphs of the square lattice, which are identified with domino tilings of the plane, and apply channels to some conjectures by Pachter.

A dominating set of a graph $G$ is a set of vertices $D$ such that for all $\nu \in V(G)$, either $\nu \in D$ or $[\nu ,d]\in E(G)$ for some $d\in D$. The cardinality-redundance of a vertex set $S$, $CR(S)$, is the number of vertices $x\in V(G)$ such that $|N[x]\cap S|\ge 2$. The cardinality-redundance of $G$ is the minimum of $CR(S)$ taken over all dominating sets $S$. A set of vertices $S$ such that $CR(S)=CR(G)$ is a ${\gamma }_{CR}$-set, and the size of a minimum ${\gamma }_{CR}$-set is denoted ${\gamma }_{CR}(G)$.

Here, we are concerned with extremal problems concerning cardinality-redundance. We give the maximum number of edges in a graph with a given number of vertices and given cardinality-redundance. In the cases that $CR(G)=0$ or $1$, we give the minimum and maximum number of edges of graphs when ${\gamma }_{CR}(G)$ is fixed, and when $CR(G)=2$, we give the maximum number of edges of graphs where ${\gamma }_{CR}(G)$ is fixed. We give the minimum and maximum values of ${\gamma }_{CR}(G)$ when the number of edges are fixed and $CR(G)=0,1$, and we give the maximum values of ${\gamma }_{CR}(G)$ when the number of edges are fixed and $CR(G)=2$.

It is known that for a maximal planar graph $G$ with order $n\ge 4$, the independence number satisfies $\frac{n}{4}\le \alpha (G)\le \frac{2n-4}{3}$. We show that the lower bound is sharp and characterize the extremal graphs for $n\le 12$. For the upper bound, we characterize the extremal graphs of all orders.

The independence number $\alpha (G)$ of a graph $G$ is the size of the largest independent set. This parameter is difficult to determine in general, but can be bounded on various graph classes. This paper considers planar and maximal planar graphs.

Constraint Programming (CP) is a method used to model and solve complex combinatorial problems. An alternative to Integer Programming for solving large-scale industrial problems, it is, under some circumstances, more efficient than IP, but its strength lies mainly in the use of predicates to model problems. This paper presents the at-least-$m$-different predicate and provides a class of facet-defining inequalities of the convex hull of integer solutions. This predicate bounds the number of values that variables in a set may receive. The paper also presents a polynomial-time separation algorithm to be used in the context of a branch-and-bound optimization approach.

Let $N_{2}DL(v)$ denote the set of degrees of vertices at distance $2$ from $v$. The $2$-neighborhood degree list of a graph is a listing of $N_{2}DL(v)$ for every vertex $v$. A degree restricted $2$-switch on edges $v_1{v}_2$ and $w_1{w}_2$, where $\mathrm{deg}(v_1)=\mathrm{deg}(w_1)$ and $\mathrm{deg}(v_2)=\mathrm{deg}(w_2)$, is the replacement of a pair of edges $v_1{v}_2$ and $w_1{w}_2$ by the edges $v_1{w}_2$ and $v_2{w}_1$, given that $v_1{w}_2$ and $v_2{w}_1$ did not appear in the graph originally. Let $G$ and $H$ be two graphs of diameter $2$ on the same vertex set. We prove that $G$ and $H$ have the same $2$-neighborhood degree list if and only if $G$ can be transformed into $H$ by a sequence of degree restricted $2$-switches.