A graph \(H\) of order \(n\) is said to be embeddable in a graph \(G\) of order \(n\), if \(G\) contains a spanning subgraph isomorphic to \(H\). It is well known that any non-star tree \(T\) of order \(n\) is embeddable in its complement (i.e. in \(K_n – E(T)\)). In the paper “Packing two copies of a tree into its fourth power” by Hamamache Kheddouci, Jean-Francois Saclé, and Mariusz Wodgniak, Discrete Mathematics 213 (2000), 169-178, it is proved that any non-star tree \(T\) is embeddable in \(T^4 – E(T)\). They asked whether every non-star tree \(T\) is embeddable in \(T^3 – E(T)\). In this paper, answering their question negatively, we show that there exist trees \(T\) such that \(T\) is not embeddable in \(T^3 – E(T)\).

The linear \(2\)-arboricity \(la_2(G)\) of a graph \(G\) is the least integer \(k\) such that \(G\) can be partitioned into \(k\) edge-disjoint forests, whose component trees are paths of length at most \(2\). We prove that \(la_2(G) \leq \lfloor \frac{\Delta(G) + 4}{2} \rfloor\) if \(G\) is an outerplanar graph with maximum degree \(\Delta(G)\).

A paired-dominating set of a graph \(G\) is a dominating set of vertices whose induced subgraph has a perfect matching. We characterize the trees having unique minimum paired-dominating sets.

Given two graphs \(G\) and \(H \subseteq G\), we consider edge-colorings of \(G\) in which every copy of \(H\) has at least two edges of the same color. Let \(f(G,H)\) be the maximum number of colors used in such a coloring of \(E(G)\). Erdős, Simonovits, and Sós determined the asymptotic behavior of \(f\) when \(G = K_n\), and \(H\) contains no edge \(e\) with \(\chi(H – e) \leq 2\). We study the function \(f(G, H)\) when \(G = K_n\), or \(K_{m,n}\), and \(H\) is \(K_{2,t}\).

This article provides some new methods of construction of two and three associate class Nested Partially Balanced Incomplete Block (NPBIB) designs. The methods are based on Latin-square association scheme, rectangular association scheme, and triangular association scheme. One method of constructing NPBIB designs has also been given by incorporating a set of new treatments in place of each treatment in a Nested Balanced Incomplete Block (NBIB) design. Exhaustive catalogues of NPBIB designs based on two and three class association schemes with \(v \leq 30\) and \(r \leq 15\) have also been prepared.

A set \(D\) of vertices in a graph \(G\) is a total dominating set if every vertex of \(G\) has at least one neighbor in \(D\). The minimum cardinality of a total dominating set of \(G\) is called the total domination number of \(G\), denoted by \(\gamma_t(G)\). A total dominating set of \(G\) with cardinality \(\gamma_t(G)\) is called a \(\gamma_t\)-set of \(G\). We characterize trees with unique \(\gamma_t\)-sets. Further, we prove that \(\gamma_t(G) \leq \frac{3}{5}n(G)\) for graphs with unique \(\gamma_t\)-sets, and we characterize all graphs with unique \(\gamma_t\)-sets where \(\gamma_t(G) = \frac{3}{5}n(G)\).

A word \(w = w_1w_2\ldots w_n\) avoids an adjacent pattern \(\tau\) iff \(w\) has no subsequence of adjacent letters having all the same pairwise comparisons as \(\tau\). In [12] and [13] the concept of words and permutations avoiding a single adjacent pattern was introduced. We investigate the probability that words and permutations of length \(n\) avoid two or three adjacent patterns.

We consider a variant of what is known as the discrete isoperimetric problem, namely the problem of minimising the size of the boundary of a family of subsets of a finite set. We use the technique of `shifting’ to provide an alternative proof of a result of Hart. This technique was introduced in the early \(1980s\) by Frankl and Füredi and gave alternative proofs of previously known classical results like the discrete isoperimetric problem itself and the Kruskal-Katona theorem. Hence our purpose is to bring Hart’s result into this general framework.

The domatic number of a graph \(G\) is the maximum number of dominating sets into which the vertex set of \(G\) can be partitioned.

We show that the domatic number of a random \(r\)-regular graph is almost surely at most \(r\), and that for \(3\)-regular random graphs, the domatic number is almost surely equal to \(3\).

We also give a lower bound on the domatic number of a graph in terms of order, minimum degree, and maximum degree. As a corollary, we obtain the result that the domatic number of an \(r\)-regular graph is at least \((r+1)/(3ln(r+1))\).