Graph pebbling is a network optimization method modeling the movement of resources in transit. A pebbling move on a connected graph \(G\) removes two pebbles from a vertex, places one on an adjacent vertex, and discards the other, with the loss analogous to packet loss in communication networks. The generalized version, \(t\)-pebbling, defines the \(t\)-pebbling number \(f_t(G)\) as the smallest integer such that, from any distribution of \(f_t(G)\) pebbles, \(t\) pebbles can be moved to any vertex \(v\) via a pebbling sequence. A graph satisfies the \(2t\)-pebbling property if \(2t\) pebbles can be transferred to \(v\) when \(2f_t(G)-q+1\) pebbles are distributed, where \(q\) is the number of occupied vertices. This paper establishes a lower bound for the rooted product of two graphs \(G\) and \(H\), sharp when one factor is a path, complete graph, or star. Further results on pebbling in triangle-free graphs are also obtained, including verification of the \(2t\)-pebbling property for rooted products involving such graphs.

It is known that null graphs are the only (regular) graphs with local antimagic chromatic 1 and 1-regular graphs are the only regular graphs without local antimagic chromatic number. In this paper, we first use matrices of size \((2m+1) \times (2k+1)\) to completely determine the local antimagic chromatic number of the join of null graphs \(O_m\) and 1-regular graphs \((2k+1)P_2\) for all \(k\ge 1, m\ge 2\). We then make use of other matrices of same size to obtain the local antimagic chromatic number of another family of tripartite graphs. Consequently, we obtained infinitely many (possibly disconnected) regular tripartite graphs with local antimagic chromatic number 3.

Let \(2\le k\in\mathbb{Z}\). We say that a total coloring of a \(k\)-regular simple graph via \(k+1\) colors is an efficient total coloring if each color yields an efficient dominating set, where the efficient domination condition applies to the restriction of each color class to the vertex set. We prove that Hamming shells of star transposition graphs and Hamming cubes have efficient total colorings. Also in this work, a focus is set upon the graphs of girths \(2k\) and \(k\). Efficient total colorings of finite connected simple cubic graphs of girth 6 are constructed. These are of two specific types, namely: (a) those whose 6-cycles use just 3 colors with antipodal monochromatic pairs of vertices or edges; (b) those whose 6-cycles do not respect item (a) so they use four colors. An orthogonality property holds for all graphs of type (a). Such orthogonality property allows further edge-half-girth colorings in the corresponding prism graphs.

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.