A complete coloring of a graph \( G \) is a proper vertex coloring of \( G \) with the property that for every two distinct colors \( i \) and \( j \) used in the coloring, there exist adjacent vertices of \( G \) colored \( i \) and \( j \). The maximum positive integer \( k \) for which \( G \) has a complete \( k \)-coloring is the achromatic number \( \psi(G) \) of \( G \).

A Grundy coloring of a graph \( G \) is a proper vertex coloring of \( G \) with the property that for every two colors (positive integers) \( i \) and \( j \) with \( i < j \), every vertex colored \( j \) has a neighbor colored \( i \). The maximum positive integer \( k \) for which a graph \( G \) has a Grundy \( k \)-coloring is the Grundy number \( \Gamma(G) \). Thus, \( 2 \leq \chi(G) \leq \Gamma(G) \leq \psi(G) \) for every nonempty graph \( G \). It is shown that if \( a, b, \) and \( c \) are integers with \( 2 \leq a \leq b \leq c \), then there exists a connected graph \( G \) with \( \chi(G) = a \), \( \Gamma(G) = b \), and \( \psi(G) = c \) if and only if \( a = b = c = 2 \) or \( b \geq 3 \).

Let \( G \) be a simple graph, and let \( p \) be a positive integer. A subset \( D \subseteq V(G) \) is a \( p \)-dominating set of the graph \( G \) if every vertex \( v \in V(G) – D \) is adjacent to at least \( p \) vertices of \( D \). The \( p \)-domination number \( \gamma_p(G) \) is the minimum cardinality among the \( p \)-dominating sets of \( G \). Note that the \( 1 \)-domination number \( \gamma_1(G) \) is the usual domination number \( \gamma(G) \).

A subset \( S \subseteq V(G) \) is said to be a total dominating set if every vertex in \( V(G) \) has at least one neighbor in \( S \), and it is a connected dominating set if the graph induced by \( S \) is connected. The total domination number \( \gamma_t(G) \) represents the cardinality of a minimum total dominating set of \( G \) and the connected domination number \( \gamma_c(G) \) the cardinality of a minimum connected dominating set.

Fink and Jacobson showed in 1985 that if \( G \) is a graph with \( \Delta(G) \geq p \geq 2 \), then \(\gamma_p(G) \geq \gamma(G) + p – 2.\)
In this paper, we will give some sufficient conditions for a graph \( G \) such that \(\gamma_p(G) \geq \gamma(G) + p – 1.\)
We will show that for block graphs \( G \) the inequality \(\gamma_p(G) \geq \gamma_t(G) + p – 2 \) is valid and that for trees \( T \) the inequality \(\gamma_p(T) \geq \gamma_c(T) + p – 1\) holds. Further, we characterize the trees \( T \) with \(\gamma_p(T) = \gamma_c(T) + p – 1,\) \(\gamma_p(T) = \gamma_t(T) + p – 2, \gamma_p(T) = \gamma_t(T) + p – 1,\) and \(\gamma_p(T) = \gamma(T) + p – 1.\)

Let \( G = (V, E) \) be a connected graph. A dominating set \( S \) of \( G \) is called a neighborhood connected dominating set (\({ncd-set}\)) if the induced subgraph \( \langle N(S) \rangle \) is connected. The minimum cardinality of an ncd-set of \( G \) is called the neighborhood connected domination number of \( G \) and is denoted by \( \gamma_{nc}(G) \). In this paper, we initiate a study of this parameter.

Let \( \lambda K_v \) be the complete multigraph, and \( G \) a finite simple graph. A \( G \)-design (\( G \)-packing, \( G \)-covering, respectively) of \( \lambda K_v \) is denoted by \( GD(v, G, \lambda) \) (\( PD(v, G, \lambda) \), \( CD(v, G, \lambda) \), respectively). In this paper, we will give some construction methods of graph packings and graph coverings, determine the existence spectrum for the \( G \)-designs of \( \lambda K_v \), and construct the maximum packings and the minimum coverings of \( \lambda K_v \) with \( G \) for any positive integer \( \lambda \). The graph \( G \) is either \( (K_4 – e) \cup P_1 \) or \( C_5 \bigodot P_1 \). Therefore, the problems of \( G \)-coverings and \( G \)-packings of \( \lambda K_v \) are solved completely when \( G \) is a graph with order \( 6 \) and \( |E(G)| \leq 6 \).

A maximal directed path in an acyclic orientation of a graph \( G \) is a path \( a_1 \to a_2 \to \cdots \to a_k \) such that \( \text{id}\; a_1 = \text{od}\; a_k = 0 \). The compression of \( G \) is the smallest integer \( k \) such that, for any acyclic orientation of \( G \), there is a maximal directed path of length at most \( k \). We characterize graphs with compression \( 1 \) and \( 2 \) and determine the compression of trees.

The generalized deBruijn graph \(dB(a,k)\) is the directed graph with \(a^k\) vertices and edges between vertices \(x = a_1, a_2, \ldots, a_k\) and \(y = b_1, b_2, \ldots, b_k\) precisely when \(a_2\cdots a_k = b_1,b_2\cdots b_{k-1}\). The deBruijn graphs can be further generalized by introducing an overlap variable \(t \leq k-1\) where the number of consecutive digits by which the vertex labels (sequences) overlap is \(t\). The \(\alpha\)-overlap graph is the underlying simple graph of the generalized deBruijn digraph with vertex label overlap \(0 t > 0\). Thus \(dB(a,k) = G(a,k,k-1)\). In this paper, we show that every \(\alpha\)-overlap graph is \(3\)-colorable for any \(a\) if \(k\) is sufficiently large. We also determine bounds on the chromatic number of the \(\alpha\)-overlap graphs if \(a\) is much larger than \(k\).