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.