A Roman dominating function on a graph \(G = (V, E)\) is a function \(f : V \to \{0,1,2\}\) satisfying the condition that every vertex \(u \in V\) for which \(f(u) = 0\) is adjacent to a vertex \(v\) for which \(f(v) = 2\). The weight of a Roman dominating function is the value \(f(V) = \sum_{u \in V} f(u)\). The Roman domination number, \(\gamma_R(G)\), of \(G\) is the minimum weight of a Roman dominating function on \(G\). In this paper, we study those graphs for which the removal of any pair of vertices decreases the Roman domination number. A graph \(G\) is said to be \emph{Roman domination bicritical} or just \(\gamma_R\)-bicritical, if \(\gamma_R(G – \{v,u\}) < \gamma_R(G)\) for any pair of vertices \(v,u \in V\). We study properties of \(\gamma_R\)-bicritical graphs, and we characterize \(\gamma_R\)-bicritical trees and unicyclic graphs.

The van der Waerden number \(W(r, k)\) is the least integer \(N\) such that every \(r\)-coloring of \(\{1, 2, \ldots, N\}\) contains a monochromatic arithmetic progression of length at least \(k\). Rabung gave a method to obtain lower bounds on \(W(2, k)\) based on quadratic residues, and performed computations on all primes no greater than \(20117\). By improving the efficiency of the algorithm of Rabung, we perform the computation for all primes up to \(6 \times 10^7\), and obtain lower bounds on \(W(2, k)\) for \(k\) between \(11\) and \(23\).

Let \( G = (V, E) \) be a graph with chromatic number \( k \). A dominating set \( D \) of \( G \) is called a chromatic transversal dominating set (ctd-set) if \( D \) intersects every color class of any \( k \)-coloring of \( G \). The minimum cardinality of a ctd-set of \( G \) is called the chromatic transversal domination number of \( G \) and is denoted by \( \gamma_{ct}(G) \). In this paper, we obtain sharp upper and lower bounds for \( \gamma_{ct} \) for the Mycielskian \( \mu(G) \) and the shadow graph \( \text{Sh}(G) \) of any graph \( G \). We also prove that for any \( c \geq 2 \), the decision problem corresponding to \( \gamma_{ct} \) is NP-hard for graphs with \( \chi(G) = c \).

Let \( G(V, E) \) be a simple graph, and let \( f \) be an integer function defined on \( V \) with \( 1 \leq f(v) \leq d(v) \) for each vertex \( v \in V \). An \( f \)-edge covered colouring is an edge colouring \( C \) such that each colour appears at each vertex \( v \) at least \( f(v) \) times. The maximum number of colours needed to \( f \)-edge covered colour \( G \) is called the \( f \)-edge covered chromatic index of \( G \) and denoted by \( \chi_{fc}'(G) \). Any simple graph \( G \) has an \( f \)-edge covered chromatic index equal to \( \delta_f \) or \( \delta_f – 1 \), where \( \delta_f = \min \left\{\left\lfloor\frac{d(v)}{f(v)}\right\rfloor : v \in V(G)\right\} \). Let \( G \) be a connected and not complete graph with \( \chi_{fc}’ = \delta_f – 1 \). If for each \( u, v \in V \) and \( e = uv \notin E \), we have \( \chi_{fc}'(G+e) > \chi_{fc}'(G) \); then \( G \) is called an \( f \)-edge covered critical graph. In this paper, some properties of \( f \)-edge covered critical graphs are discussed. It is proved that if \( G \) is an \( f \)-edge covered critical graph, then for each \( u, v \in V \) and \( e = uv \notin E \) there exists \( w \in \{u, v\} \) with \( d(w) \leq \delta_f(f(w) + 1) – 2 \) such that \( w \) is adjacent to at least \( \max \left\{d(w) – \delta_f f(w) + 1, (f(w) + 2)d(w) – \delta_f(f(w) + 1)^2 + f(w) + 3\right\} \) vertices which are all \( \delta_f \)-vertices in \( G \).