A radio labeling of a graph \( G \) is a mapping \( f : V(G) \to \{0, 1, 2, \dots\} \) such that \( |f(u)-f(v)| \geq \text{diam}(G) + 1 – d(u,v) \) for every pair of distinct vertices \( u,v \) of \( G \), where \( \text{diam}(G) \) is the diameter of \( G \) and \( d(u,v) \) is the distance between \( u \) and \( v \) in \( G \). The radio number \( \text{rn}(G) \) of \( G \) is the smallest integer \( k \) such that \( G \) admits a radio labeling \( f \) with \( \max\{f(v) : v \in V(G)\} = k \). In this paper, we give a lower bound for the radio number of the Cartesian product of a tree and a complete graph and give two necessary and sufficient conditions for the sharpness of the lower bound. We also give three sufficient conditions for the sharpness of the lower bound. We determine the radio number of the Cartesian product of a level-wise regular tree and a complete graph which attains the lower bound. The radio number of the Cartesian product of a path and a complete graph derived in [B. M. Kim, W. Hwang, and B. C. Song, Radio number for the product of a path and a complete graph, J. Comb. Optim., 30 (2015), 139–149] can be obtained using our results in a short way.

Let \( G \) be a connected graph with \( m \) edges. The density of a nontrivial subgraph \( H \) with \( \omega(H) \) components is \( d(H) = \frac{|E(H)|}{|V(H)| – \omega(H)} \). A graph \( G \) is uniformly dense if for any nontrivial subgraph \( H \) of \( G \), \( d(H) \leq d(G) \). For each cyclic ordering \( o=(e_1, e_2, \dots, e_m) \) of \( E(G) \), let \( h(o) \) be the largest integer \( k \) such that every \( k \) cyclically consecutive elements in \( o \) induce a forest in \( G \); and the largest \( h(o) \), taken among all cyclic orderings of \( G \), is denoted by \( h(G) \). A cyclic ordering \( o \) of \( G \) is a cyclic base ordering if \( h(o) = |V(G)| – \omega(G) \). In [15], Kajitani et al. proved that every connected nontrivial graph with a cyclic base ordering is uniformly dense, and conjectured that every uniformly dense graph has a cyclic base ordering. This motivates the study of \( h(G) \). In this paper, we investigate the value of \( h \) for some families of graphs and determine all connected graphs \( G \) with \( h(G) \leq 2 \).

An open-locating-dominating set of a graph models a detection system for a facility with a possible “intruder” or a multiprocessor network with a possible malfunctioning processor. A “sensor” or “detector” is assumed to be installed at a subset of vertices where each can detect an intruder or a malfunctioning processor in its neighborhood, but not at its own location. We consider a fault-tolerant variant of an open-locating-dominating set called an error-correcting open-locating-dominating set, which can correct a false-positive or a false-negative signal from a detector. In particular, we prove the problem of finding a minimum error-correcting open-locating-dominating set in an arbitrary graph is NP-complete. Additionally, we characterize the existence criteria for an error-correcting open-locating-dominating set in an arbitrary graph. We also consider extremal graphs that require every vertex to be a detector and minimum error-correcting open-locating-dominating sets in infinite grids.

Let \( G = (V, E) \) be a graph with vertex set \( V \) and edge set \( E \). A set \( S \subset V \) is a dominating set if every vertex in \( V – S \) is adjacent to at least one vertex in \( S \), an independent set if no two vertices in \( S \) are adjacent, and a total dominating set if every vertex in \( V \) is adjacent to at least one vertex in \( S \). The domatic number \( \text{dom}(G) \), idomatic number \( \text{idom}(G) \), and total domatic number \( \text{tdom}(G) \), of a graph \( G \) equal the maximum order \( k \) of a partition \( \pi = \{V_1, V_2, \ldots, V_k\} \) of \( V \) into {dominating sets, independent dominating sets, total dominating sets}, respectively. A queens graph \( Q_n \) is a graph defined on the \( n^2 \) squares of an \( n \)-by-\( n \) chessboard, such that two squares are adjacent if and only if a queen on one square can move to the other square in one move, that is, the two squares lie on a common row, column, or diagonal. In this note, we determine the value of these three numbers for \( Q_n \) for the first several values of \( n \). In addition, we introduce the concepts of graphs being \( \gamma \)-domatic, \( i \)-domatic, \( \alpha \)-domatic, \( \Gamma \)-domatic, \( \gamma_t \)-domatic, and \( \Gamma_t \)-domatic.

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, \ldots, 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, \ldots, 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, \ldots \) from an asymptotic perspective.