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.

Multi-sender authentication codes allow a group of senders to construct an authenticated message for a receiver such that the receiver can verify the authenticity of the received message. In this paper, we construct one multi-sender authentication code from polynomials over finite fields. Some parameters and the probabilities of deceptions of this code are also compute

For graphs \(G\) and \(H\), Ramsey number \(R(G, H)\) is the smallest natural number \(n\) such that no \((G, H)\)-free graph on \(n\) vertices exists. In 1981, Burr [5] proved the general lower bound \(R(G, H) \geq (n – 1)(\chi(H) – 1) + \sigma(H)\), where \(G\) is a connected graph of order \(n\), \(\chi(H)\) denotes the chromatic number of \(H\) and \(\sigma(H)\) is its chromatic surplus, namely, the minimum cardinality of a color class taken over all proper colorings of \(H\) with \(\chi(H)\) colors. A connected graph \(G\) of order \(n\) is called good with respect to \(H\), \(H\)-good, if \(R(G, H) = (n – 1)(\chi(H) – 1) + \sigma(H)\). The notation \(tK_m\) represents a graph with \(t\) identical copies of complete graph \(K_m\). In this note, we discuss the goodness of cycle \(C_n\) with respect to \(tK_m\) for \(m, t \geq 2\) and sufficiently large \(n\). Furthermore, it is also provided the Ramsey number \(R(G, tK_m)\), where \(G\) is a disjoint union of cycles.