We give necessary and sufficient conditions for the existence of 2-colorable \(G\)-designs for each \(G\) that is connected, simple and has at most 5 edges.

In this paper we examine the existence problem for cyclic Mendelsohn quadruple systems (briefly CMQS) and we prove that a CMQS of order \(v\) exists if and only if \(v \equiv 1 \pmod{4}\). Further we study the maximum number \(m_a(v)\) of pairwise disjoint (on the same set) CMQS’s of order \(v\) each having the same \(v\)-cycle as an automorphism. We prove that, for every \(v \equiv 1 \pmod{4}\), \(2v-8 \leq m_4(v) \leq v^2 – 11v + z\), where \(z = 32\) if \(v \equiv 1\) or \(5 \pmod{12}\) and \(z = 30\) if \(v \equiv 9 \pmod{12}\), and that \(m_4(5) = 2\), \(m_4(9) = 12\), \(50 \leq m_4(13) \leq 58\).

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.