Steiner triple systems admitting automorphisms whose disjoint cyclic decomposition consist of two cycles are explored. We call such systems bicyclic . Several necessary conditions are given. Sufficient conditions are given when the length of the smaller cycle is \(7\).

The \(\Delta\)-subgraph \(G_\Delta \) of a simple graph \(G\) is the subgraph induced by the vertices of maximum degree of \(G\). In this paper, we obtain some results about the construction of a graph \(G\) if the graph \(G\) is Class 2 and the structure of \(G_\Delta \) is particularly simple.

The automorphism group of a graph acts on its cocycle space over any field. The orbits of this group action will be counted in case of finite fields. In particular, we obtain an enumeration of non-equivalent edge cuts of the graph.

We give necessary and sufficient conditions on the order of a Steiner triple system admitting an automorphism \(\pi\), consisting of \(1\) large cycle, several cycles of length \(4\) and a fixed point.

A graph \(G = (V, E)\) is said to be elegant if it is possible to label its vertices by an injective mapping \(g\) into \(\{0, 1, \dots, |E|\}\) such that the induced labeling \(h\) on the edges defined for edge \(x, y\) by \(h(x, y) = g(x) + g(y) \mod (|E| + 1)\) takes all the values in \(\{1, \dots, |E|\}\). In the first part of this paper, we prove the existence of a coloring of \(K_n\) with a omnicolored path on \(n\) vertices as subgraph, which had been conjectured by Hastman [2].
In the second part we prove that the cycle on \(n\) vertices is elegant if and only if \(n \neq 1 \pmod{4}\) and we give a new construction of an elegant labeling of the path \(P_n\), where \(n \neq 4\).

A round robin tournament on \(q\) players in which draws are not permitted is said to have property \(P(n, k)\) if each player in any subset of \(n\) players is defeated by at least \(k\) other players. We consider the problem of determining the minimum value \(F(n, k)\) such that every tournament of order \(q \geq F(n, k)\) has property \(P(n, k)\). The case \(k = 1\) has been studied by Erdős, G. and E. Szekeres, Graham and Spencer, and Bollobás. In this paper we present a lower bound on \(F(n, k)\) for the case of Paley tournaments.

Upper and lower bounds are established for the toughness of the generalized Petersen graphs \(G(n,2)\) for \(n \geq 5\), and all non-isomorphic disconnecting sets that achieve the toughness are presented for \(5 \leq n \leq 15\). These results also provide an infinite class of \(G(n,2)\) for which the toughness equals \(\frac{5}{4}\), namely when \(n \equiv 0 (\mod 7)\).

Let \(m\) be a double occurrence word (i.e., each letter occurring in \(m\) occurs precisely twice). An alternance of \(m\) is a non-ordered pair \(uw\) of distinct letters such that we meet alternatively \(\dots v \dots w \dots v \dots w \dots\) when reading \(m\). The alternance graph \(A(m)\) is the simple graph whose vertices are the letters of \(m\) and whose edges are the alternances of \(m\). We define a transformation of double occurrence words such that whenever \(A(m) = A(n)\), \(m\) and \(n\) are related by a sequence of these transformations.

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.

We obtain a new characterization, by a configuration theorem, of the Miquelian geometries among the finite inversive (= Möbius) planes of even order. The main tool used is a characterization due to J. Tits of elliptic ovoids in three-dimensional projective space,

Let \(E_n\) denote the minimum number of edges in a graph that contains every tree with \(n\) edges. This article provides two sets of data concerning \((n+1)\)-vertex graphs with \(E_n\) edges for each \(n \leq 11\): first, a minimum set of trees with \(n\) edges such that all trees with \(n\) edges are contained in such a graph whenever it contains the trees in the minimum set; second, all mutually nonisomorphic graphs that contain all trees with \(n\) edges.

A graph \(H\) is \underline{collapsible} if for every even subset \(W \subseteq V(H)\), \(H\) has a spanning connected subgraph whose set of odd-degree vertices is \(W\). In a graph \(G\), there is a unique collection of maximal collapsible subgraphs, and when all of them are contracted, the resulting contraction of \(G\) is a reduced graph. Reduced graphs have been shown to be useful in the study of supereulerian graphs, hamiltonian line graphs, and double cycle covers, (see[2], [3], [4] [6] ), among others. It has been noted that subdividing an edge of a collapsible graph may result in a noncollapsible graph. In this note we characterize the reduced graphs of elementary subdivision of collapsible graphs of diameter at most two. We also obtain a converse of a result of Catlin [3] when restricted to graphs of diameter at most two. The main result is used to study some hamiltonian property of line graphs.

The \(F\)-free chromatic number \(\chi(M:-F)\) of a graph \(M\) is defined as the least number of classes in a partition of the vertices of \(M\) such that \(F\) does not occur as an induced subgraph in the subgraph induced by any of the colour classes. Two graphs \(G\) and \(H\) are called chromatically related if, for each positive integer \(k\), there exists a graph \(M\) such that \(\chi(M:-G) = \chi(M:-H) = k\), and distantly related whenever a chain of such relatednesses exists between them. Using a basic theorem of Folkman [3], we show that every two graphs on at least two vertices are distantly related.

BIBRC (balanced incomplete block with nested rows and columns) designs were introduced by Singh and Dey [1979] and these designs were mostly obtained by trial and error. Agrawal and Prasad [1983] gave some systematic methods of construction of these designs. We provide further systematic and general methods of construction of BIBRC designs in the present note.

An exponent bound is presented for abelian \((p^{i+j}, p^i, p^{i+j},p^j)\) relative difference sets: this bound can be met for \(i \leq j\).

A smallest transversal of a \(k\)-graph (or \(k\)-uniform hypergraph) is any smallest set of vertices that intersects all edges. We investigate smallest transversals of small (up to ten vertex) \(3\)-graphs. In particular, we show how large the smallest transversal of small \(3\)-graphs can be as a function of the number of edges and vertices. Also, we identify all \(3\)-graphs with up to nine vertices that have largest smallest transversals. This work is related to a problem of Turán, and to the covering problem. In particular, extremal \(3\)-graphs correspond to covering designs with blocks of size \(n-3\).

We determine those triples \((g, u, k)\) for which there exists a pair of group divisible designs with block size \(3\), each on the same \(u\) groups of size \(g\), having exactly \(k\) blocks in common.