The induced path number \( \rho(G) \) of a graph \( G \) is defined as the minimum number of subsets into which the vertex set of \( G \) can be partitioned so that each subset induces a path. A Nordhaus-Gaddum type result is a (tight) lower or upper bound on the sum (or product) of a parameter of a graph and its complement. If \( G \) is a subgraph of \( H \), then the graph \( H – E(G) \) is the complement of \( G \) relative to \( H \). In this paper, we consider Nordhaus-Gaddum type results for the parameter \( \rho \) when the relative complement is taken with respect to the complete bipartite graph \( K_{m,n} \).

Rado constructed a (simple) denumerable graph \( R \) with the positive integers as vertex set with the following edges: For given \( m \) and \( n \) with \( m < n \), \( m \) is adjacent to \( n \) if \( n \) has a \( 1 \) in the \( m \)'th position of its binary expansion. It is well known that \( R \) is a universal graph in the set \( \mathcal{I} \) of all countable graphs (since every graph in \( \mathcal{I} \) is isomorphic to an induced subgraph of \( R \)) and that \( R \) can be characterized using this notion and that of being homogeneous and having the extension property. In this paper, we extend these notions to arbitrary induced-hereditary properties (of graphs), relate them to the construction of a universal graph for any such property, and obtain results which remind one of some characterizations of \( R \).

In this note, we prove that for any tree \( T \), \( \gamma_{\leq2}(T) \leq \gamma_\gamma(T) \leq ir(T) \leq \gamma(T) \), where \( \gamma_{\leq2}(G) \) is the distance-2 domination number, \( ir(T) \) is the (lower) irredundance number, \( \gamma(T) \) is the domination number, and \( \gamma_\gamma(T) \), newly defined here, equals the minimum cardinality of a set of vertices that dominates a minimum dominating set of \( T \).

A graph is \((k, l)\)-colorable if its vertex set can be partitioned into \( k \) independent sets and \( l \) cliques. A graph is chordal if it does not contain any induced cycle of length at least four. A theorem by Hell et al. states that a chordal graph is \((k, l)\)-colorable if and only if it does not contain \((l+1)K_{k+1}\) as an induced subgraph. Presented here is a short alternative proof of this result, using the characterization of chordal graphs via perfect elimination orderings.

A subset \( X \) of the vertex set of a graph \( G \) is a secure dominating set of \( G \) if \( X \) is a dominating set of \( G \) and if, for each vertex \( u \) not in \( X \), there is a neighboring vertex \( v \) of \( u \) in \( X \) such that the swap set \( (X – \{v\}) \cup \{u\} \) is again a dominating set of \( G \). The secure domination number of \( G \), denoted by \( \gamma_s(G) \), is the cardinality of a smallest secure dominating set of \( G \). In this paper, we present two algorithms (a branch-and-reduce algorithm as well as a branch-and-bound algorithm) for determining the secure domination number of a general graph \( G \) of order \( n \). The worst-case time complexities of both algorithms are \( \mathcal{O}(2^{n-s-\sum_{i=1}^{k}(|\mathcal{R}_i|-1)}) \), where \( s \) is the number of support vertices in \( G \) and \( \mathcal{R}_i, \ldots, \mathcal{R}_k \) are the redundancy classes of \( G \) (two vertices are in the same redundancy class if they are adjacent and share the same closed neighborhood which forms a clique in \( G \)).

The distinguishing chromatic number of a graph \( G \) is the least integer, \( \chi_D(G) \), for which \( G \) has a coloring of its vertices so that adjacent vertices receive different colors, and the identity is the only automorphism of \( G \) that preserves vertex colors. Our focus is on determining the distinguishing chromatic numbers of wreath products of graphs, extending the work of Tang. We prove that if \( C_n \) is a cycle with \( n \) vertices and \( P_n \) is a path with \( n \) vertices, then \( \chi_D(C_n[G]) \) and \( \chi_D(P_n[G]) \) can be found for any connected graph \( G \). We also obtain an upper bound on \( \chi_D(T[G]) \) when \( T \) is a tree and \( G \) is any connected graph. Some of our results depend on the notion of inequivalent colorings. Cheng introduces inequivalent colorings and provides a formula for computing the number of inequivalent distinguishing \( k \)-colorings of a rooted tree. We add to this work by obtaining an expression for computing the number of inequivalent distinguishing \( k \)-colorings of a cycle.