A radio labeling of a simple connected graph \( G \) is a function \( f: V(G) \to \mathbb{Z}^+ \) such that for every two distinct vertices \( u \) and \( v \) of \( G \),
$$distance(u, v) + |f(u) – f(v)| \geq 1 + diameter(G).$$
The radio number of a graph \( G \) is the smallest integer \( M \) for which there exists a labeling \( f \) with \( f(v) \leq M \) for all \( v \in V(G) \). An edge-balanced caterpillar graph is a caterpillar graph that has an edge such that removing this edge results in two components with an equal number of vertices. In this paper, we determine the radio number of particular edge-balanced caterpillars as well as improve the lower bounds of the radio number of other edge-balanced caterpillars.

It is known that an ordered \(\rho\)-labeling of a bipartite graph \( G \) with \( n \) edges yields a cyclic \( G \)-decomposition of \( K_{2nx+1} \) for every positive integer \( x \). We extend the concept of an ordered \(\rho\)-labeling to bipartite digraphs and show that an ordered directed \(\rho\)-labeling of a bipartite digraph \( D \) with \( n \) arcs yields a cyclic \( D \)-decomposition of \( K_{nx+1}^* \) for every positive integer \( x \). We also find several classes of bipartite digraphs that admit an ordered directed \(\rho\)-labeling.

Compressed sensing (CS), which is a rising technique of signal processing, successfully manages the huge expenditure of increasing the sampling rate as well as the intricate issues to our work. Hence, more and more attention has been paid to CS during recent years. In this paper, we construct a family of error-correcting pooling designs based on singular linear space over finite fields, which can be efficiently applied to signal processing in terms of CS.

It is proven that for all positive integers \( k \), \( n \), and \( r \), every sufficiently large positive integer is the sum of \( r \) or more \( k \)th powers of distinct elements of \(\{n,n + 1,n + 2,\ldots\}\). The case \( n = 1 \) is the conjecture in the title of [1].

In 1770, Waring conjectured that for each positive integer \( k \) there exists a \( g(k) \) such that every positive integer is a sum of \( g(k) \) or fewer \( k \)th powers of positive integers. Hilbert proved this theorem in 1909, giving rise to Waring’s problem, which asks, for each \( k \), what is the smallest \( g(k) \) such that the statement holds. For further details, see [3].

As a natural question arising from this problem, Johnson and Laughlin [1] proposed what they called an anti-Waring conjecture, which is the following: If \( k \) and \( r \) are positive integers, then every sufficiently large positive integer is the sum of \( r \) or more distinct \( k \)th powers of positive integers. When this holds for a pair \( k, r \), let \( N(k,r) \) denote the smallest positive integer such that each integer \( n \) greater than or equal to \( N(k,r) \) is the sum of \( r \) or more \( k \)th powers of distinct positive integers. As noted in [1], it is easy to see that, for all \( r \), \( N(1,r) = 1 + 2 + \cdots + r = \frac{r(r+1)}{2} \). It is also shown in [1] that \( N(2,1) = N(2, 2) = N(2,3) = 129 \).

Johnson and Laughlin further posed the question of whether given any positive integers \( k \), \( n \), \( r \), there exists an integer \( N(k,n,r) \) such that every integer \( z \) greater than or equal to \( N(k,n,r) \) can be written as a sum of \( r \) or more distinct elements from the set \( \{m^k \mid m \in \mathbb{N}, m \geq n\} \). The aim of this paper is to prove both this statement and the anti-Waring conjecture to be true.

We consider an optimization problem motivated by the tradeoff between connectivity and resilience in key predistribution schemes (KPS) for sensor networks that are based on certain types of combinatorial designs. For a specific class of designs, we show that there is no real disadvantage in requiring the underlying design to be regular.

We define three new pebbling parameters of a connected graph \( G \), the \( r \)-, \( g \)-, and \( u \)-\emph{critical pebbling numbers}. Together with the pebbling number, the optimal pebbling number, the number of vertices \( n \) and the diameter \( d \) of the graph, this yields \( 7 \) graph parameters. We determine the relationships between these parameters. We investigate properties of the \( r \)-critical pebbling number, and distinguish between greedy graphs, thrifty graphs, and graphs for which the \( r \)-critical pebbling number is \( 2^d \).

A set \( S \subset V \) of vertices in a graph \( G = (V, E) \) is called open irredundant if for every vertex \( v \in S \) there exists a vertex \( w \in V \setminus S \) such that \( w \) is adjacent to \( v \) but to no other vertex in \( S \). The upper open irredundance number \( OIR(G) \) equals the maximum cardinality of an open irredundant set in \( G \). A real-valued function \( g: V \to [0,1] \) is called open irredundant if for every vertex \( v \in V \), \( g(v) > 0 \) implies there exists a vertex \( w \) adjacent to \( v \) such that \( g(N[w]) = 1 \). An open irredundant function \( g \) is maximal if there does not exist an open irredundant function \( h \) such that \( g \neq h \) and \( g(v) \leq h(v) \), for every \( v \in V \). The fractional upper open irredundance number equals \( OIR_f(G) = \sup\{|g|: g \text{ is an open irredundant function on } G\} \). In this paper we prove that for any graph \( G \), \( OIR(G) = OIR_f(G) \).

A graph \( G \) is \( H \)-saturated if \( G \) does not contain \( H \) as a subgraph, but the addition of any edge between two nonadjacent vertices in \( G \) results in a copy of \( H \) in \( G \). The saturation number \( \operatorname{sat}(n, H) \) is the smallest possible number of edges in an \( n \)-vertex \( H \)-saturated graph. The values of saturation numbers for small graphs and \( H \) are obtained computationally, and some general results for specific path unions are also obtained.

A path \( P \) in a graph \( G \) is said to be a degree monotone path if the sequence of degrees of the vertices of \( P \) in the order in which they appear on \( P \) is monotonically non-decreasing. The length of the longest degree monotone path in \( G \) is denoted by \( \operatorname{mp}(G) \). This parameter was first studied in an earlier paper by the authors where bounds in terms of other parameters of \( G \) were obtained.

In this paper we concentrate on the study of how \( \operatorname{mp}(G) \) changes under various operations on \( G \). We first consider how \( \operatorname{mp}(G) \) changes when an edge is deleted, added, contracted or subdivided. We similarly consider the effects of adding or deleting a vertex. We sometimes restrict our attention to particular classes of graphs.

Finally we study \( \operatorname{mp}(G \times H) \) in terms of \( \operatorname{mp}(G) \) and \( \operatorname{mp}(H) \) where \( \times \) is either the Cartesian product or the join of two graphs.

In all these cases we give bounds on the parameter \( \operatorname{mp} \) of the modified graph in terms of the original graph or graphs and we show that all the bounds are sharp.

Given a graph \( G \), a \( k \)-ranking is a labeling of the vertices such that any path connecting two vertices with the same label contains a vertex with a larger label. A \( k \)-ranking is minimal if and only if reducing any label violates the ranking property. The arank number of a graph \( \psi_r(G) \), is the maximum \( k \) such that \( G \) has a minimal \( k \)-ranking. The arank number of a cycle was first investigated by Kostyuk and Narayan. They determined precise arank numbers for most cycles, and determined the arank number within \( 1 \) for all other cases. In this paper we introduce a new concept called the flanking number, which is used to solve all open cases. We prove that \( \psi_r(C_n) = \lfloor\log_2(n + 1)\rfloor + \lfloor\log_2 \left(\frac{n+2}{3}\right)\rfloor + 1 \) for all \( n > 6 \), which completely solves the problem that has been open since \( 2003 \).