In this paper, we consider a variation of toughness, and prove stronger results for the existence of \([a, b]\)-factors. Furthermore, we show that the results are sharp in some sense.

A decomposition \( \mathcal{D} \) of a graph \( H \) by a graph \( G \) is a partition of the edge set of \( H \) such that the subgraph induced by the edges in each part of the partition is isomorphic to \( G \). The intersection graph \( I(\mathcal{D}) \) of the decomposition \( \mathcal{D} \) has a vertex for each part of the partition and two parts \( A \) and \( B \) are adjacent if and only if they share a common node in \( H \). If \( I(\mathcal{D}) \cong H \), then \( \mathcal{D} \) is an automorphic decomposition of \( H \). If \( n(G) = \chi(H) \) as well, then we say that \( \mathcal{D} \) is a fully automorphic decomposition. In this paper, we examine the question of whether a fully automorphic host will have an even degree of regularity. We also give several examples of fully automorphic decompositions as well as necessary conditions for their existence.

A modular \(k\)-coloring, \(k \geq 2\), of a graph \(G\) without isolated vertices is a coloring of the vertices of \(G\) with the elements in \(\mathbb{Z}_k\) (where adjacent vertices may be colored the same) having the property that for every two adjacent vertices in \(G\) the sums of the colors of their neighbors are different in \(\mathbb{Z}_k\). The minimum \(k\) for which \(G\) has a modular \(k\)-coloring is the modular chromatic number mc\((G)\) of \(G\). It is known that \(2 \leq \text{mc}(T) \leq 3\) for every nontrivial tree \(T\). We present an efficient algorithm that computes the modular chromatic number of a given tree.

In this note, we consider the \(i\)-block intersection graphs (\(i\)-BIG) of a universal friendship \(3\)-hypergraph and show that they are pancyclic for \(i = 1,2\). We also show that the \(1\)-BIG of a universal friendship \(3\)-hypergraph is Hamiltonian-connected.

We study samples \(\Gamma = (\Gamma_1, \ldots, \Gamma_n)\) of length \(n\) where the letters \(\Gamma_i\) are independently generated according to the geometric distribution \(\mathbb{P}(\Gamma_j = i) = pq^{i-1}\), for \(1 \leq j \leq n\), with \(p+q=1\) and \(0<p<1\). An \({up-smooth\; sample}\) \(\Gamma\) is a sample such that \(\Gamma_{i+1}- \Gamma_i \leq 1\). We find generating functions for the probability that a sample of \(n\) geometric variables is up-smooth, with or without a specified first letter. We also extend the up-smooth results to words over an alphabet of \(k\) letters and to compositions of integers. In addition, we study smooth samples \(T\) of geometric random variables, where the condition now is \(|\Gamma_{i+1}- \Gamma_i| \leq 1\).

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

For a connected graph \(G\) of order \(3\) or more and an edge coloring \(c: E(G) \to \mathbb{Z}_k\) (\(k \geq 2\)) where adjacent edges may be colored the same, the color sum \(s(v)\) of a vertex \(v\) of \(G\) is the sum in \(\mathbb{Z}_k\) of the colors of the edges incident with \(v\). The edge coloring \(c\) is a modular \(k\)-edge coloring of \(G\) if \(s(u) \neq s(v)\) in \(\mathbb{Z}_k\) for all pairs \(u, v\) of adjacent vertices in \(G\). The modular chromatic index \(\chi_m'(G)\) of \(G\) is the minimum \(k\) for which \(G\) has a modular \(k\)-edge coloring. It is shown that \(\chi(G) \leq \chi_m'(G) \leq \chi(G)+1\) for every connected graph \(G\) of order at least 3, where \(\chi(G)\) is the chromatic number of \(G\). Furthermore, it is shown that \(\chi_m'(G) = \chi(G) + 1\) if and only if \(\chi(G) \equiv 2 \pmod{4}\) and every proper \(\chi(G)\)-coloring of \(G\) results in color classes of odd size.