Various enumeration problems for classes of simply generated families of trees have been the object of investigation in the past. We mention the enumeration of independent subsets, connected subsets or matchings for instance. The aim of this paper is to show how combinatorial problems of this type can also be solved for rooted trees and trees, which enables us to take better account of isomorphisms. As an example, we will determine the average number of independent vertex subsets of trees and binary rooted trees (every node has outdegree \(\leq 2\)).

In this paper, first we introduce the concept of a \({connected}\) graph homomorphism as a homomorphism for which the inverse image of any edge is either empty or a connected graph, and then we concentrate on chromatically connected (resp. chromatically disconnected) graphs such as \(G\) for which any \(\chi(G)\)-colouring is a connected (resp. disconnected) homomorphism to \(K_{\chi(G)}\).

In this regard, we consider the relationships of the new concept to some other notions as uniquely-colourability. Also, we specify some classes of chromatically disconnected graphs such as Kneser graphs \(KG(m,n)\) for which \(m\) is sufficiently larger than \(n\), and the line graphs of non-complete class II graphs.

Moreover, we prove that the existence problem for connected homomorphisms to any fixed complete graph is an NP-complete problem.

We show that every \(2\)-connected cubic graph of order \(n > 8\) admits a \(P_3\)-packing of at least \(\frac{9n}{11}n\) vertices. The proof is constructive, implying an \(O(M(n))\) time algorithm for constructing such a packing, where \(M(n)\) is the time complexity of the perfect matching problem for \(2\)-connected cubic graphs.

The locally twisted cube \(LTQ_n\) is a newly introduced interconnection network for parallel computing. As a variant of the hypercube \(Q_n\), \(LTQ_n\) has better properties than \(Q_n\) with the same number of links and processors. Yang, Megson and Evans Evans [Locally twisted cubes are \(4\)-pancyclic, Applied Mathematics Letters, \(17 (2004), 919-925]\) showed that \(LTQ_n\) contains a cycle of every length from \(4\) to \(2^n\). In this note, we improve this result by showing that every edge of \(LTQ_n\) lies on a cycle of every length from \(4\) to \(2^n\) inclusive.

Necessary and sufficient conditions are given for the existence of a \((K_3 + e, \lambda)\)-group divisible design of type \(g^tu^1\).

A \(\lambda\)-design on \(v\) points is a set of \(v\) subsets (blocks) of a \(v\)-set such that any two distinct blocks meet in exactly \(\lambda\) points and not all of the blocks have the same size. Ryser’s and Woodall’s \(\lambda\)-design conjecture states that all \(4\)-designs can be obtained from symmetric designs by a complementation procedure. In this paper, we establish feasibility criteria for the existence of \(\lambda\)-designs with two block sizes in the form of integrality conditions, equations, inequalities, and Diophantine equations involving various parameters of the designs. We use these criteria and a computer to prove that the \(\lambda\)-design conjecture is true for all \(\lambda\)-designs with two block sizes with \(v \leq 90\) and \(\lambda \neq 45\).

In this paper, we consider the relationships between the sums of the Fibonacci and Lucas numbers and \(1\)-factors of bipartite graphs.

We define extended orthogonal sets of \(d\)-cubes and show that they are equivalent to a class of orthogonal arrays, to geometric nets and a class of codes. As a corollary, an upper bound for the maximal number of \(d\)-cubes in an orthogonal set is obtained.

For two given graphs \(G_1\) and \(G_2\), the \({Ramsey\; number}\) \(R(G_1, G_2)\) is the smallest integer \(n\) such that for any graph \(G\) of order \(n\), either \(G\) contains \(G_1\) or the complement of \(G\) contains \(G_2\). Let \(P_n\) denote a path of order \(n\) and \(W_{m}\) a wheel of order \(m+1\). Chen et al. determined all values of \(R(P_n, W_{m})\) for \(n \geq m-1\). In this paper, we establish the best possible upper bound and determine some exact values for \(R(P_n, W_{m})\) with \(n \leq m-2\).

A container \(C(x,y)\) is a set of vertex-disjoint paths between vertices \(z\) and \(y\) in a graph \(G\). The width \(w(C(x,y))\) and length \(L(C(x,y))\) are defined to be \(|C(x,y)|\) and the length of the longest path in \(C(x,y)\) respectively. The \(w\)-wide distance \(d_w(x,y)\) between \(x\) and \(y\) is the minimum of \(L(C(x,y))\) for all containers \(C(x,y)\) with width \(w\). The \(w\)-wide diameter \(d_w(G)\) of \(G\) is the maximum of \(d_w(x,y)\) among all pairs of vertices \(x,y\) in \(G\), \(x \neq y\). In this paper, we investigate some problems on the relations between \(d_w(G)\) and diameter \(d(G)\) which were raised by D.F. Hsu \([1]\). Some results about graph equation of \(d_w(G)\) are proved.