A graph \(G\) is a sum graph if there is a labeling \(o\) of its vertices with distinct positive integers, so that for any two distinct vertices \(u\) and \(v\), \(uv\) is an edge of \(G\) if and only if \(\sigma(u) +\sigma(v) = \sigma(w)\) for some other vertex \(w\). Every sum graph has at least one isolated vertex (the vertex with the largest label). Harary has conjectured that any tree can be made into a sum graph with the addition of a single isolated vertex. We prove this conjecture.

An \(H\)-decomposition of a graph \(G\) is a representation of \(G\) as an edge disjoint union of subgraphs, all of which are isomorphic to another graph \(H\). We study the case where \(H\) is \(P_3 \cup tK_2\) – the vertex disjoint union of a simple path of length 2 (edges) and \(t\) isolated edges – and prove that a set of three obviously necessary conditions for \(G = (V, E)\) to admit an \(H\)-decomposition, is also sufficient if \(|E|\) exceeds a certain function of \(t\). A polynomial time algorithm to test \(H\)-decomposability of an input graph \(G\) immediately follows.

In this paper we consider group divisible designs with equal-sized holes \((HGDD)\) which is a generalization of modified group divisible designs \([1]\) and \(HMOLS\). We prove that the obvious necessary conditions for the existence of the \(HGDD\) is sufficient when the block size is three, which generalizes the result of Assaf[1].

An obvious necessary condition for the existence of an almost resolvable \(B(k,k-1;v)\) is \(v \equiv 1 \pmod{k}\). We show in this paper that the necessary condition is also sufficient for \(k = 5\) or \(k = 6\), possibly excepting \(8\) values of \(v\) when \(k = 5\) and \(3\) values of \(v\) when \(k = 6\).

This paper gives two sufficient conditions for a \(2\)-connected graph to be pancyclic. The first one is that the degree sum of every pair of nonadjacent vertices should not be less than \(\frac{n}{2} + \delta\). The second is that the degree sum of every triple of independent vertices should not be less than \(n + \delta\), where \(n\) is the number of vertices and \(\delta\) is the minimum degree of the graph.

In this paper we will consider the Ramsey numbers for paths and cycles in graphs with unordered as well as ordered vertex sets.

Suppose that \(R = (V, A)\) is a diregular bipartite tournament of order \(p \geq 8\). Denote a cycle of length \(k\) by \(C_k\). Then for any \(e \in A(R)\), \(w \in V(R) \setminus V(e)\), there exists a pair of vertex-disjoint cycles \(C_4\) and \(C_{p-4}\) in \(R\) with \(e \in C_4\) and \(w \in C_{p-4}\), except \(R\) is isomorphic to a special digraph \(\tilde{F}_{4k}\).

We construct all four-chromatic triangle-free graphs on twelve vertices, and a triangle-free, uniquely three-colourable graph.

Let \(K\) be a maximal block of a graph \(G\) and let \(x\) and \(y\) be two nonadjacent vertices of \(G\). If \(|V(X)| \leq \frac{1}{2}(n+3)\) and \(x\) and \(y\) are not cut vertices, we show that \(x\) is not adjacent to \(y\) in the closure \(c(G)\) of \(G\). We also show that, if \(x, y \notin V(K)\), then \(x\) is not adjacent to \(y\) in \(c(G)\).

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.

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.

In this paper, we give some recursive constructions for large sets of disjoint group-divisible designs with block size \(3\). In particular, we construct new infinite classes of large sets for designs having group-size two. These large sets have applications in cryptography to the construction of perfect threshold schemes.

A decomposition into non-isomorphic matchings, or \(DINIM\) for short, is a partition of the edges of a graph \(G\) into matchings of different sizes. As a special case of our results, we prove that if a graph \(G\) has at least \((2\chi’ – 2)\chi’ + 1\) edges, where \(\chi’ = \chi'(G)\) is the chromatic index of \(G\), then \(G\) has a \(DINIM\). In particular, the \(n\)-dimensional cube, \(Q_n\), \(n \geq 4\), has a \(DINIM\). These results confirm two conjectures which appeared in Chinn and Richter [3].

We present a permutation group whose orbits classify isomorphism of covering projections of the complete graph with \(4\) vertices. Two structure theorems concerning this group are proved.

Constructions have been completed which improve the lower bounds for \(R(4,6)\), \(R(5,6)\) and \(R(3,12)\).

Let \(G\) be a graph with minimum degree \(\delta\). For each \(i = 1, 2, \ldots, \delta \), let \(a_i(G)\) (resp. \(\alpha^*_i(G)\)) denote the smallest integer \(k\) such that \(G\) has an \([i, k]\)-factor (resp. a connected \([i, k]\)-factor). Denote by \(G_n\) a complete \(n\)-partite graph. In this paper, we determine the value of \(\alpha_t(G_n)\), and show that \(0 \leq \alpha^*_1(G_n) – \alpha(G_n) \leq 1\) and \(\alpha^*_i(G_n) = a_i(G_n)\) for each \(i = 2, 3, \ldots, \delta\).

An oriented (or ordered) triple means either a Mendelsohn or a transitive triple. An oriented (or ordered) triple system of order \(v\), briefly OTS(\(v\)), is a pair \((V, B)\), where \(V\) is a \(v\)-set and \(B\) is a collection of oriented triples of elements of \(V\), such that every ordered pair of distinct elements of \(V\) belongs to exactly one member of \(B\). It is known that an OTS(\(v\)) exists if and only if \(v \equiv 0, 1 \pmod{3}\). An OTS(\(v\)) is cyclic if it admits an automorphism consisting of a single cycle of length \(v\); an OTS(\(v\)) is rotational if it admits an automorphism consisting of a single fixed point and one cycle of length \(v-1\). In this note we give some constructions of OTS(\(v\))’s which allow to determine the spectrum of cyclic and of rotational OTS(\(v\))’s.

It is shown that the maximal number of pairwise edge disjoint trees of order seven in the complete graph \(K_n\), and the minimum number of trees of order seven, whose union is \(K_n\), are \(\left\lfloor\frac{n(n-1)}{12}\right\rfloor\) and \(\left\lceil\frac{n(n-1)}{12}\right\rceil,n\geq 11\), respectively. (\(\lfloor x\rfloor\) denotes the largest integer not exceeding \(x\) and \(\lceil x\rceil\) the least integer not less than \(x\)).

It is unknown whether or not there exists a \([51, 5, 33; 3]\)-code (meeting the Griesmer bound). The purpose of this paper is to show that there is no \([51, 5, 33; 3]\)-code.

The Hitting Set problem is investigated in relation to restrictions imposed on the cardinality of subsets and the frequency of element occurences in the subsets. It is shown that the Hitting Set subproblem where each subset has cardinality \(C\) for fixed \(C \geq 2\) and the frequency of each element is exactly \(f\) for fixed \(f \geq 3\) remains NP-complete, but the problem becomes polynomial when \(f \leq 2\). The restriction of the Vertex Cover problem to \(f\)-regular graphs for \(f \geq 3\) remains NP-complete.

Hill and Newton showed that there exists a \([20, 6, 12; 3]\)-code, and that the weight distribution of a \([20,5, 12; 3]\)-code is unique. However, it is unknown whether or not a code with these parameters is unique. Recently, Hamada and Helleseth showed that a \([19, 4, 12; 3]\)-code is unique up to equivalence, and characterized this code using a characterization of \(\{21, 6; 3, 3\}\)-minihypers. The purpose of this paper is to show, using the geometrical structure of the \([19, 4, 12; 3]\)-code, that exactly two non-isomorphic \([20, 5, 12; 3]\)-codes exist.