In this paper, we prove the existence of \(22\) new \(3\)-designs on \(26\) and \(28\) points. The base of the constructions are two designs with a small maximum size of the intersection of any two blocks.

A large set of KTS(\(v\)), denoted by LKTS(\(v\)), is a collection of (\(v-2\)) pairwise disjoint KTS(\(v\)) on the same set. In this article, some new LKTS(\(v\)) is constructed.

Let \(G\) be a graph with \(v\) vertices. If there exists a list of colors \(S_1, S_2, \ldots, S_v\) on its vertices, each of size \(k\), such that there exists a unique proper coloring for \(G\) from this list of colors, then \(G\) is called a uniquely \(k\)-list colorable graph. We prove that a connected graph is uniquely \(2\)-list colorable if and only if at least one of its blocks is not a cycle, a complete graph, or a complete bipartite graph. For each \(k\), a uniquely \(k\)-list colorable graph is introduced.

A supergraph \(H\) of a graph \(G\) is called tree-covered if \(H – E(G)\) consists of exactly \(|V(G)|\) vertex-disjoint trees, with each tree having exactly one point in common with \(G\). In this paper, we show that if a graph \(G\) can be packed in its complement and if \(H\) is a tree-covered supergraph of \(G\), then \(G\) itself is self-packing unless \(H\) happens to be a member of a specified class of graphs. This is a generalization of earlier results that almost all trees and unicyclic graphs can be packed in their complements.

Let \(T = (V,A)\) be an oriented graph with \(n\) vertices. \(T\) is completely strong path-connected if for each arc \((a,b) \in A\) and \(k\) (\(k = 2, \ldots, n-1\)), there is a path from \(b\) to \(a\) of length \(k\) (denoted by \(P_k(a,b)\)) and a path from \(a\) to \(b\) of length \(k\) (denoted by \(P’_k(a,b)\)) in \(T\). In this paper, we prove that a connected local tournament \(T\) is completely strong path-connected if and only if for each arc \((a,b) \in A\), there exist \(P_2(a,b)\) and \(P’ _2(a,b)\) in \(T\), and \(T\) is not of \(T_1 \ncong T_0\)-\(D’_8\)-type digraph and \(D_8\).

It was proved by Ellingham \((1984)\) that every permutation graph either contains a subdivision of the Petersen graph or is edge-\(3\)-colorable. This theorem is an important partial result of Tutte’s Edge-\(3\)-Coloring Conjecture and is also very useful in the study of the Cycle Double Cover Conjecture. The main result in this paper is that every permutation graph contains either a subdivision of the Petersen graph or two \(4\)-circuits and therefore provides an alternative proof of the theorem of Ellingham. A corollary of the main result in this paper is that every uniquely edge-\(3\)-colorable permutation graph of order at least eight must contain a subdivision of the Petersen graph.

In this paper, the \(k\)-exponent and the \(k\)th upper multiexponent of primitive nearly reducible matrices are obtained and a bound on the \(k\)th lower multiexponent of this kind of matrices is given.

We call a simple \(t-(v,k)\) trade with maximum volume a maximal trade. In this paper, except for \(v = 6m+5\), \(m \geq 3\), maximal \(2-(v, 3)\) trades for all \(v\)’s are determined. In the latter case a bound for the volume of these trades is given.

Balanced ternary and generalized balanced ternary designs are constructed from any \((v, b, r, k)\) designs. These results generalise the earlier results of Diane Donovan ( 1985 ).

A graph is called \(K_{1,r}\)-free if it does not contain \(K_{1,r}\) as an induced subgraph. In this paper we generalize a theorem of Markus for Hamiltonicity of \(2\)-connected \(K_{1,r}\)-free (\(r \geq 5\)) graphs and present a sufficient condition for \(1\)-tough \(K_{1,r}\)-free (\(r \geq 4\)) graphs to be Hamiltonian.

Minimum degree two implies the existence of a cycle. Minimum degree \(3\) implies the existence of a cycle with a chord. We investigate minimum degree conditions to force the existence of a cycle with \(k\) chords.

Let \(T = (V, E)\) be a tree on \(|V| = n\) vertices. \(T\) is graceful if there exists a bijection \(f : V \to \{0,1,\dots, n-1\}\) such that \(\{|f(u) – f(v)| \mid uv \in E\} = \{1,2,\dots,n-1\}\). If, moreover, \(T\) contains a perfect matching \(M\) and \(f\) can be chosen in such a way that \(f(u) + f(v) = n-1\) for every edge \(uv \in M\) (implying that \(\{|f(u) – f(v)| \mid uv \in M\} = \{1,3,\dots,n-1\}\)), then \(T\) is called strongly graceful. We show that the well-known conjecture that all trees are graceful is equivalent to the conjecture that all trees containing a perfect matching are strongly graceful. We also give some applications of this result.

Let \(D\) be an acyclic digraph. The competition graph of \(D\) has the same set of vertices as \(D\) and an edge between vertices \(u\) and \(v\) if and only if there is a vertex \(x\) in \(D\) such that \((u,x)\) and \((v,x)\) are arcs of \(D\). The competition-common enemy graph of \(D\) has the same set of vertices as \(D\) and an edge between vertices \(u\) and \(v\) if and only if there are vertices \(w\) and \(x\) in \(D\) such that \((w,u), (w,v), (u,x)\), and \((v,x)\) are arcs of \(D\). The competition number (respectively, double competition number) of a graph \(G\), denoted by \(k(G)\) (respectively, \(dk(G)\)), is the smallest number \(k\) such that \(G\) together with \(k\) isolated vertices is a competition graph (respectively, competition-common enemy graph) of an acyclic digraph.

It is known that \(dk(G) \leq k(G) + 1\) for any graph \(G\). In this paper, we give a sufficient condition under which a graph \(G\) satisfies \(dk(G) \leq k(G)\) and show that any connected triangle-free graph \(G\) with \(k(G) \geq 2\) satisfies that condition. We also give an upper bound for the double competition number of a connected triangle-free graph. Finally, we find an infinite family of graphs each member \(G\) of which satisfies \(k(G) = 2\) and \(dk(G) > k(G)\).

A \(k \times v\) double Youden rectangle (DYR) is a type of balanced Graeco-Latin design where each Roman letter occurs exactly once in each of the \(k\) rows, where each Greek letter occurs exactly once in each of the \(v\) columns, and where each Roman letter is paired exactly once with each Greek letter. The other properties of a DYR are of balance, and indeed the structure of a DYR incorporates that of a symmetric balanced incomplete block design (SBIBD). Few general methods of construction of DYRs are known, and these cover only some of the sizes \(k \times v\) with \(k = p\) (odd) or \(p+1\), and \(v = 2p + 1\). Computer searches have however produced DYRs for those such sizes, \(p \leq 11\), for which the existence of a DYR was previously in doubt. The new DYRs have cyclic structures. A consolidated table of DYRs of sizes \(p \times (2p +1)\) and \((p +1) \times (2p +1)\) is provided for \(p \leq 11\); for each of several of the sizes, DYRs are given for different inherent SBIBDs.

Block-intersection graphs of Steiner triple systems are considered. We prove that the block-intersection graphs of non-isomorphic Steiner triple systems are themselves non-isomorphic. We also prove that each Steiner triple system of order at most \(15\) has a Hamilton decomposable block-intersection graph.

A directed graph \(G\) is primitive if there exists a positive integer \(k\) such that for every pair \(u, v\) of vertices of \(G\) there is a walk from \(u\) to \(v\) of length \(k\). The least such \(k\) is called the exponent of \(G\). The exponent set \(E_n\) is the set of all integers \(k\) such that there is a primitive graph \(G\) on \(n\) vertices whose exponent is \(k\).

A simple inequality involving the number of components in an arbitrary graph becomes an equality precisely when the graph is chordal. This leads to a mechanism by which any graph parameter, if always at least as large as the number of components, corresponds to a subfamily of chordal graphs. As an example, the domination number corresponds to the well-studied family of \(P_4, C_4\)-free graphs.

In this paper, we will be concerned with graphs \(G\) satisfying: \(G\) is isometrically embeddable in a hypercube; \(|C(a,b)| = |C(b,a)|\) for every edge \([a,b]\) of \(G\). where \(C(a,b)\) is the set of vertices nearer to \(a\) than to \(b\). Some properties of such graphs are shown; in particular, it is shown that all such graphs \(G\) are \(3\)-connected if \(G\) has at least two edges and \(G\) is not a cycle.

We improve upon Caro’s general polynomial characterizations, all in terms of modified line graphs, restricted to decomposing a graph into isomorphic subgraphs \(H\) with two edges. Firstly, we solve the problem for a multigraph; secondly, we decrease the polynomial bound on complexity if \(H = 2K_2\) and provide an original sufficient condition which can be verified in linear time if \(H = P_3\).

It has been shown by Sittampalam and Keedwell that weak critical sets exist for certain latin squares of order six and that previously claimed examples (for certain latin squares of order \(12\)) are incorrect. This led to the question raised in the title of this paper. Our purpose is to show that five is the smallest order for which weakly completable critical sets exist. In the process of proving this result, we show that, for each of the two types of latin square of order four, all minimal critical sets are of the same type.

We show that if \(G\) is a \((2k-1)\)-connected graph \((k \geq 2)\) with radius \(r\), then \(r \leq \left\lfloor \frac{|V(G)|+2k+9}{2k}\right\rfloor\).

A Cayley digraph \({Cay}(G, S)\) of a finite group \(G\) is isomorphic to another Cayley digraph \({Cay}(G, T)\) for each automorphism \(\sigma\) of \(G\). We will call \({Cay}(G, S)\) a CI-graph if, for each Cayley digraph \({Cay}(G,T)\), whenever \({Cay}(G, S) \cong {Cay}(G,T)\) there exists an automorphism \(\sigma\) of \(G\) such that \(S^\sigma = T\). Further, for a positive integer \(m\), if all Cayley digraphs of \(G\) of out-valency \(m\) are CI-graphs, then \(G\) is said to have the \(m\)-DCI property. This paper shows that for any positive integer \(m\), if a finite abelian group \(G\) has the \(m\)-DCI property, then all Sylow subgroups of \(G\) are homocyclic.

A directed graph operation called pushing a vertex is studied. When a vertex is pushed, the orientation of each of its incident edges is reversed. We consider the problems of pushing vertices so as to produce: strongly connected digraphs semi-connected digraphs acyclic digraphs NP-completeness results are shown for each problem. It is shown that it is possible to create a directed path between any two vertices in a digraph; additional positive results and characterizations are shown for: tournaments outerplanar digraphs Hamiltonian cycles.

A Freeman-Youden rectangle (FYR) is a Graeco-Latin row-column design consisting of a balanced superimposition of two Youden squares. There are well known infinite series of FYRs of size \(q \times (2q+1)\) and \((q+1) \times (2q+1)\) where \(2q+1\) is a prime power congruent to \(3\) (modulo \(4\)). However, Preece and Cameron [9] additionally gave a single FYR of size \(7 \times 15\). This isolated example is now shown to belong to one of a set of infinite series of FYRs of size \(q \times (2q+1)\) where \(q\), but not necessarily \(2q+1\), is a prime power congruent to \(3\) (modulo \(4\)), \(q > 3\); there are associated series of FYRs of size \((q+1) \times (2q+1)\). Both the old and the new methodologies provide FYRs of sizes \(q \times (2q+1)\) and \((q+1) \times (2q+1)\) where both \(q\) and \(2q+1\) are congruent to \(3\) (modulo \(4\)), \(q > 3\); we give special attention to the smallest such size, namely \(11 \times 23\).

Let \(n_4(k,d)\) and \(d_4(n, k)\) denote the smallest value of \(n\) and the largest value of \(d\), respectively, for which there exists an \([n, k, d]\) code over the Galois field \(GF(4)\). It is known (cf. Boukliev [1] and Table B.2 in Hamada [6]) that (1) \(n_4(5, 179) =240\) or \(249\), \(n_4(5,181) = 243\) or \(244, n_4(5, 182) = 244\) or \(245, n_4(5, 185) = 248\) or \(249\) and (2) \(d_4(240,5) = 178\) or \(179\) and \(d_4(244,5) = 181\) or \(182\). The purpose of this paper is to prove that (1) \(74(5,179) = 241, n_4(5,181) = 244, n_4(5,182) = 245, n_4(5, 185) = 249\) and (2) \(d_4(240, 5) = 178\) and \(d_4(244,5) = 181\).

Let \(T_n\) denote any rooted tree with \(n\) nodes and let \(p = p(T_n)\) and \(q = q(T_n)\) denote the number of nodes at even and odd distance, respectively, from the root. We investigate the limiting distribution, expected value, and variance of the numbers \(D(T_n) = |p – q|\) when the trees \(T_n\) belong to certain simply generated families of trees.

In this paper, magic labelings of graphs are considered. These are labelings of the edges with integers such that the sum of the labels of incident edges is the same for all vertices. We particularly study positive magic labelings, where all labels are positive and different. A decomposition in terms of basis-graphs is described for such labelings. Basis-graphs are studied independently. A characterization of an algorithmic nature is given, leading to an integer linear programming problem. Some relations with other graph theoretical subjects, like vertex cycle covers, are discussed.