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 \).

A DI-pathological graph is a graph in which every minimum dominating set intersects every maximal independent set. DI-pathological graphs are related to the Inverse Domination Conjecture; hence, it is useful to characterize properties of them. One characterization question is how large or small a graph can be relative to the domination number. Two useful characterizations of size seem relevant, namely the number of vertices and the number of edges. In this paper, we provide two results related to this question. In terms of the number of vertices, we show that every connected, DI-pathological graph has at least \(2\gamma(G) + 4\) vertices except \(K_{3,3}\), \(K_{3,4}\), and six graphs on nine vertices and show that our lower bound is best possible. We then show that with one exception, every connected, DI-pathological graph with no isolated vertices has at least \(2\gamma(G) + 5\) edges and show that our lower bound is best possible.

A dominating set in a graph \( G \) is a subset \( S \) of vertices such that any vertex not in \( S \) is adjacent to some vertex of \( S \). The domination number, \( \gamma(G) \), of \( G \) is the minimum cardinality of a dominating set. A dominating set of cardinality \( \gamma(G) \) is called a \( \gamma(G) \)-set. A fair dominating set in a graph \( G \) (or FD-set) is a dominating set \( S \) such that all vertices not in \( S \) are dominated by the same number of vertices from \( S \); that is, every two vertices not in \( S \) have the same number of neighbors in \( S \). The fair domination number, \( fd(G) \), of \( G \) is the minimum cardinality of an FD-set. A fair dominating set of \( G \) of cardinality \( fd(G) \) is called an \( fd(G) \)-set. We say that \( fd(G) \) and \( \gamma(G) \) are \emph{strongly equal} and denote by \( fd(G) \equiv \gamma(G) \), if every \( \gamma(G) \)-set is an \( fd(G) \)-set. In this paper, we provide a constructive characterization of trees \( T \) with \( fd(T) \equiv \gamma(T) \).

We consider edge-colorings of complete graphs in which each color induces a subgraph that does not contain an induced copy of \( K_{1,t} \), for some \( t \geq 3 \). It turns out that such colorings, if the underlying graph is sufficiently large, contain spanning monochromatic \( k \)-connected subgraphs. Furthermore, there exists a color, say blue, such that every vertex has very few incident edges in colors other than blue.