In this paper it is shown that the number of induced subgraphs (the set of edges is induced by the set of nodes) of trees of size \(n\) satisfy a central limit theorem and that multivariate asymptotic expansions can be obtained. In the case of planted plane trees, \(N\)-ary trees, and non-planar rooted labelled trees, explicit formulae can be given. Furthermore, the average size of the largest component of induced subgraphs in trees of size \(n\) is evaluated asymptotically.

We introduce a new concept called algebraic equivalence of sigraphs to study the family of sigraphs with all eigenvalues \(\geq -2\). First, we prove that any sigraph whose least eigenvalue is \(-2\) contains a proper subgraph such that both generate the same lattice in \({R}^n\). Next, we present a characterization of the family of sigraphs with all eigenvalues \(> -2\) and obtain Witt’s classification of root lattices and the well known theorem which classifies the first mentioned family by using root systems \(D_n, n \in {N} \) and \(E_8 \). Then, we prove that any sigraph whose least eigenvalue is less than \(-2\), contains a subgraph whose least eigenvalue is \(-2\). Using this, we characterize the families of sigraphs represented by the above root systems. Finally, we prove that a sigraph generating \(E_n\) ( \(n=7\) or 8) contains a subgraph generating \(E_{n-1}\) . In short, this new concept takes the central role in unifying and explaining various aspects of the theory of sigraphs represented by root systems and in giving simpler and shorter proofs of earlier known results including Witt’s theorem and also in proving new results.

Let \(T_{g}(m,n)\) (respectively, \(P_{g}(m, n)\)) be the number of rooted maps, on an orientable (respectively, non-orientable) surface of type \(g\), which have \(m\) vertices and \(n\) faces. Bender, Canfield and Richmond [3] obtained asymptotic formulas for \(T_{g}(m,n)\) and \(P_{g}(m,n)\) when \(\epsilon \leq m/n \leq 1/\epsilon\) and \(m,n \to \infty\). Their formulas cannot be extended to the extreme case when \(m\) or \(n\) is fixed. In this paper, we shall derive asymptotic formulas for \(T_{g}(m,n)\) and \(P_{g}(m,n)\) when \(m\) is fixed and derive the distribution for the root face valency. We also show that their generating functions are algebraic functions of a certain form. By the duality, the above results also hold for maps with a fixed number of faces.

Consider the following two-person game on the graph \(G\). Player I and II move alternatingly. Each move consists in coloring a yet uncolored vertex of \(G\) properly using a prespecified set of colors. The game ends when some player can no longer move. Player I wins if all of \(G\) is colored. Otherwise Player II wins. What is the minimal number \(\gamma(G)\) of colors such that Player I has a winning strategy? Improving a result of Bodlaender [1990] we show \(\gamma(T) \leq 4\) for each tree \(T\). We, furthermore, prove \(\gamma(G) = O(\log |G|)\) for graphs \(G\) that are unions of \(k\) trees. Thus, in particular, \(\gamma(G) = O(\log |G|)\) for the class of planar graphs. Finally we bound \(4(G)\) by \(3w(G) – 2\) for interval graphs \(G\). The order of magnitude of \(\gamma(G)\) can generally not be improved for \(k\)-fold trees. The problem remains open for planar graphs.

We examine properties of a class of hypertrees, occurring in probability, which are described by sequences of subscripts.

We give, among other results, a new method to construct for each positive integer \(n\) a class of orthogonal designs \( {OD}(4^{n+1};m;4^n m,4^n m,4^n m,4^n m)\), \(m=2^a 10^b 26^c +4^n+1\), \(a,b,c\) non-negative integers.

We verify that \(6\) more of the tum squares of order \(10\) cannot be completed to a triple of mutually orthogonal Latin squares of order \(10\). We find a pair of orthogonal Latin squares of order \(10\) with \(6\) common transversals, \(5\) of which have only a single intersection, and a pair with \(7\) common transversals.

We give a complete solution to the existence problem for subdesigns in complementary \(\mathrm{P}_3\)-decompositions, where \(\mathrm{P}_3\) denotes the path of length three. As a corollary we obtain the spectrum for incomplete designs with block size four and \(\lambda = 2\), having one hole.