Super-simple, Pan-orientable, and Pan-decomposable BIBDs with Block Size 4 and Related Structures

Let v, k, and μ be positive integers. A tournament T of order k, briefly k-tournament, is a directed graph on k vertices in which there is exactly one directed edge between any two vertices. A (v, k, λ = 2μ)-BIBD is called T-orientable if for each of its blocks B, it is possible to replace B by a copy of T on the set B so that every ordered pair of distinct points appears in exactly μ k-tournaments. A (v, k, λ = 2μ)-BIBD is called pan-orientable if it is T-orientable for every possible k-tournament T. In this paper, we continue the earlier investigations and complete the spectrum for (v, 4, λ = 2μ)-BIBDs which possess both the pan-orientable property and the pan-decomposable property first introduced by Granville et al. (Graphs Comb 5:57–61, 1989). For all μ, we are able to show that the necessary existence conditions are sufficient. When λ = 2 and v > 4, our designs are super-simple, that is they have no two blocks with more than two common points. One new corollary to this result is that there exists a (v, 4, 2)-BIBD which is both super-simple and directable for all v ≡ 1, 4 (mod 6), v > 4. Finally, we investigate the existence of pan-orientable, pan-decomposable (v, 4, λ = 2μ)-BIBDs with a pan-orientable, pan-decomposable (w, 4, λ = 2μ)-BIBD as a subdesign; here we obtain complete results for λ = 2, 4, but there remain several open cases for λ = 6 (mostly for v < 4w), and the case λ = 12 still has to be investigated.     

Existence of GBRDs with block size 4 and BRDs with block size 5

Chaudhry et al. (J Stat Plann Inference 106:303–327, 2002) have examined the existence of BRD(v, 5, λ)s for \({\lambda \in \{4, 10, 20\}}\). In addition, Ge et al. (J Combin Math Combin Comput 46:3–45, 2003) have investigated the existence of \({{\rm GBRD}(v,4,\lambda; \mathbb{G}){\rm s}}\) when \({\mathbb{G}}\) is a direct product of cyclic groups of prime orders. For the first problem, necessary existence conditions are (i) v ≥ 5, (ii) λ(v ? 1) ≡ 0 (mod4), (iii) λ v(v ? 1) ≡ 0 (mod 40), (iv) λ ≡ 0 (mod 2). We show these are sufficient, except for \({v=5, \lambda \in \{4,10\}}\). For the second problem, we improve the known existence results. Five necessary existence conditions are (i) v ≥ 4, (ii) \({\lambda \equiv 0\;({\rm mod}\,|\mathbb{G}|)}\), (iii) λ(v ? 1) ≡ 0 (mod 3), (iv) λ v(v ? 1) ≡ 0 (mod 4), (v) if v = 4 and \({|\mathbb{G}| \equiv 2\;({\rm mod}\,4)}\) then λ ≡ 0 (mod 4). We show these conditions are sufficient, except for \({\lambda = |\mathbb{G}|, (v,|\mathbb{G}|) \in \{(4,3), (10,2), (5,6), (7,4)\}}\) and possibly for \({\lambda = |\mathbb{G}|, (v,|\mathbb{G}|) \in \{(10,2h), (5,6h), (7,4h)\}}\) with h ≡ 1 or 5 (mod 6), h > 1.     

Small Uniformly Resolvable Designs for Block Sizes 3 and 4

A uniformly resolvable design (URD) is a resolvable design in which each parallel class contains blocks of only one block size k, such a class is denoted k‐pc and for a given k the number of k‐pcs is denoted r_k. In this paper, we consider the case of block sizes 3 and 4 (both existent). We use v to denote the number of points, in this case the necessary conditions imply that v ≡ 0 (mod 12). We prove that all admissible URDs with v < 200 points exist, with the possible exceptions of 13 values of r₄ over all permissible v. We obtain a URD({3, 4}; 276) with r₄ = 9 by direct construction use it to and complete the construction of all URD({3, 4}; v) with r₄ = 9. We prove that all admissible URDs for v ≡ 36 (mod 144), v ≡ 0 (mod 60), v ≡ 36 (mod 108), and v ≡ 24 (mod 48) exist, with a few possible exceptions. Recently, the existence of URDs for all admissible parameter sets with v ≡ 0 (mod 48) was settled, this together with the latter result gives the existence all admissible URDs for v ≡ 0 (mod 24), with a few possible exceptions.     

Super‐simple resolvable balanced incomplete block designs with block size 4 and index 3

The necessary conditions for the existence of a super‐simple resolvable balanced incomplete block design on v points with k = 4 and λ = 3, are that v ≥ 8 and v ≡ 0 mod 4. These conditions are shown to be sufficient except for v = 12. © 2003 Wiley Periodicals, Inc.     

Completely reducible super-simple designs with block size four and related super-simple packings

A design is said to be super-simple if the intersection of any two blocks has at most two elements. A super-simple design \({\mathcal{D}}\) with point set X, block set \({\mathcal{B}}\) and index λ is called completely reducible super-simple (CRSS), if its block set \({\mathcal{B}}\) can be written as \({\mathcal{B}=\bigcup_{i=1}^{\lambda} \mathcal{B}_i}\), such that \({\mathcal{B}_i}\) forms the block set of a design with index unity but having the same parameters as \({\mathcal{D}}\) for each 1 ≤ i ≤ λ. It is easy to see, the existence of CRSS designs with index λ implies that of CRSS designs with index i for 1 ≤ i ≤ λ. CRSS designs are closely related to q-ary constant weight codes (CWCs). A (v, 4, q)-CRSS design is just an optimal (v, 6, 4)_q+1 code. On the other hand, CRSS group divisible designs (CRSSGDDs) can be used to construct q-ary group divisible codes (GDCs), which have been proved useful in the constructions of q-ary CWCs. In this paper, we mainly investigate the existence of CRSS designs. Three neat results are obtained as follows. Firstly, we determine completely the spectrum for a (v, 4, 3)-CRSS design. As a consequence, a class of new optimal (v, 6, 4)₄ codes is obtained. Secondly, we give a general construction for (4, 4)-CRSSGDDs with skew Room frames, and prove that the necessary conditions for the existence of a (4, 2)-CRSSGDD of type g ^u are also sufficient except definitely for \({(g,u)\in \{(2,4),(3,4),(6,4)\}}\). Finally, we consider the related optimal super-simple (v, 4, 2)-packings and show that such designs exist for all v ≥ 4 except definitely for \({v\in \{4,5,6,9\}}\).     

An Implicit Degree Condition for Pancyclicity of Graphs

Zhu, Li and Deng introduced in 1989 the definition of implicit degree of a vertex v in a graph G, denoted by id(v), by using the degrees of the vertices in its neighborhood and the second neighborhood. And they obtained sufficient conditions with implicit degrees for a graph to be hamiltonian. In this paper, we prove that if G is a 2–connected graph of order n ≥ 3 such that id(v) ≥ n/2 for each vertex v of G, then G is pancyclic unless G is bipartite, or else n = 4r, r ≥ 2 and G is in a class of graphs F _4r defined in the paper.     

Resolvable balanced incomplete block designs with subdesigns of block size 4

In this paper, we look at resolvable balanced incomplete block designs on v points having blocks of size 4, briefly (v,4,1) RBIBDs. The problem we investigate is the existence of (v,4,1) RBIBDs containing a (w,4,1) RBIBD as a subdesign. We also require that each parallel class of the subdesign should be in a single parallel class of the containing design. Removing the subdesign gives an incomplete RBIBD, i.e., an IRB(v,w). The necessary conditions for the existence of an IRB(v,w) are that v?4w and . We show these conditions are sufficient with a finite number (179) of exceptions, and in particular whenever and whenever w?1852.We also give some results on pairwise balanced designs on v points containing (at least one) block of size w, i.e., a (v,{K,w^*},1)-PBD.If the list of permitted block sizes, K₅, contains all integers of size 5 or more, and v,w∈K₅, then a necessary condition on this PBD is v?4w+1. We show this condition is not sufficient for any w?5 and give the complete spectrum (in v) for 5?w?8, as well as showing the condition v?5w is sufficient with some definite exceptions for w=5 and 6, and some possible exceptions when w=15, namely 77?v?79. The existence of this PBD implies the existence of an IRB(12v+4,12w+4).If the list of permitted block sizes, K₁₍₄₎, contains all integers , and v,w∈K₁₍₄₎, then a necessary condition on this PBD is v?4w+1. We show this condition is sufficient with a finite number of possible exceptions, and in particular is sufficient when w?1037. The existence of this PBD implies the existence of an IRB(3v+1,3w+1).     

Block designs with large holes and α -resolvable BIBDs

In a (v, k, λ: w) incomplete block design (IBD) (or PBD [v, {k, w^*}. λ]), the relation v ≥ (k ? 1)w + 1 must hold. In the case of equality, the IBD is referred to as a block design with a large hole, and the existence of such a configuration is equivalent to the existence of a λ-resolvable BIBD(v ? w, k ? 1, λ). The existence of such configurations is investigated for the case of k = 5. Necessary and sufficient conditions are given for all v and λ ? 2 (mod 4), and for λ ≡ 2 mod 4 with 11 possible exceptions for v. © 1993 John Wiley & Sons, Inc.     

Super‐simple resolvable balanced incomplete block designs with block size 4 and index 2

The necessary conditions for the existence of a super‐simple resolvable balanced incomplete block design on v points with block size k = 4 and index λ = 2, are that v ≥ 16 and . These conditions are shown to be sufficient. © 2006 Wiley Periodicals, Inc. J Combin Designs 15: 341–356, 2007     

Enclosings of λ-fold 4-cycle systems

In this paper we solve the problem of enclosing a λ-fold 4-cycle system of order v into a (λ + m)-fold 4-cycle system of order v + u for all m > 0 and u ≥ 1. An ingredient is constructed that is of interest on its own right, namely the problem of finding equitable partial 4-cycle systems of λ K _v . This supplementary solution builds on a result of Raines and Staniszlo.     

Two Conjectures on Graceful Digraphs

A digraph D with p vertices and q arcs is labeled by assigning a distinct integer value g(v) from {0,1, … , q} to each vertex v. The vertex values, in turn, induce a value g(u, v) on each arc (u, v) where g(u, v) = (g(v)? g(u))(mod q + 1). If the arc values are all distinct then the labeling is called a graceful labeling of a digraph. Bloom and Hsu (SIAM J Alg Discr Methods 6:519–536, 1985) conjectured that, all unicyclic wheels are graceful. Also, Zhao et al. (J Prime Res Math 4:118–126, 2008) conjectured that, for any positive even n and any integer m ≥ 14, the digraph ${n-\overrightarrow{C_m}}$ is graceful. In this paper, we prove both the conjectures.     

Incomplete perfect mendelsohn designs with block size 4 and holes of size 2 and 3

Let v, k, and n be positive integers. An incomplete perfect Mendelsohn design, denoted by k-IPMD(v, n), is a triple (X, Y, ??) where X is a v-set (of points), Y is an n-subset of X, and ?? is a collection of cyclically ordered k-subsets of X (called blocks) such that every ordered pair (a, b) ∈ (X × X)\(Y × Y) appears t-apart in exactly one block of ?? and no ordered pair (a,b) ∈ Y × Y appears in any block of ?? for any t, where 1 ≤ t ≤ k ? 1. In this article, the necessary conditions for the existence of a 4-IPMD(v, n), namely (v ? n) (v ? 3n ? 1) ≡ 0 (mod 4) and v ≥ 3n + 1, are shown to be sufficient for the case n = 3. For the case n = 2, these conditions are sufficient except for v = 7 and with the possible exception of v = 14,15,18,19,22,23,26,27,30. The latter result provides a useful application to the problem relating to the packing of perfect Mendelsohn designs with block size 4. © 1994 John Wiley & Sons, Inc.     

Linear 2-Arboricity of Planar Graphs with Neither 3-Cycles Nor Adjacent 4-Cycles

Let G be a planar graph with neither 3-cycles nor adjacent 4-cycles. We prove that if G is connected and δ(G) ≥ 2, then G contains an edge uv with d(u) + d(v) ≤ 7 or a 2-alternating cycle. By this result, we obtain that G’s linear 2-arboricity ${la_{2}(G)\leq\lceil\frac{\Delta(G)+1}{2}\rceil+4.}$ .     

Incomplete perfect mendelsohn designs with block size 4 and one hole of size 7

Let v,k, and n be positive integers. An incomplete perfect Mendelsohn design, denoted by k-IPMD(v,n), is a triple (X, Y, ??) where X is a v-set (of points), Y is an n-subset of X, and ?? is a collection of cyclically ordered k-subsets of X (called blocks) such that every ordered pair (a, b) ∈ (X × X)?(Y × Y) appears t-apart in exactly one block of ?? and no ordered pair (a,b) ∈ Y × Y appears in any block of ?? for any t, where 1 ≤ t ≤ k ? 1. In this article, we obtain conclusive results regarding the existence of 4-IPMD(v,7) where the necessary conditions are v = 2 or 3(mod 4) and v ≥ 22. We also provide an application to the problem relating to coverings of PMDs with block size 4. © 1993 John Wiley & Sons, Inc.     

Generalized Bhaskar Rao Designs with Block Size 3 over Finite Abelian Groups

We show that if G is a finite Abelian group and the block size is 3, then the necessary conditions for the existence of a (v,3,λ;G) GBRD are sufficient. These necessary conditions include the usual necessary conditions for the existence of the associated (v,3,λ) BIBD plus λ≡ 0 (mod|G|), plus some extra conditions when |G| is even, namely that the number of blocks be divisible by 4 and, if v = 3 and the Sylow 2-subgroup of G is cyclic, then also λ≡ 0 (mod2|G|).     

Further results on the existence of nested orthogonal arrays

Nested orthogonal arrays provide an option for designing an experimental setup consisting of two experiments, the expensive one of higher accuracy being nested in a larger and relatively less expensive one of lower accuracy. We denote by OA_(λ, μ)(t, k, (v, w)) (or OA(t, k, (v, w)) if λ = μ = 1) a (symmetric) orthogonal array OA _λ (t, k, v) with a nested OA _μ (t, k, w) (as a subarray). It is proved in this article that an OA(t, t + 1,(v, w)) exists if and only if v ≥ 2w for any positive integers v, w and any strength t ≥ 2. Some constructions of OA_(λ, μ)(t, k, (v, w))′s with λ ≠ μ and k ? t > 1 are also presented.     

Block-transitive designs in affine spaces

This paper deals with block-transitive t-(v, k, λ) designs in affine spaces for large t, with a focus on the important index λ = 1 case. We prove that there are no non-trivial 5-(v, k, 1) designs admitting a block-transitive group of automorphisms that is of affine type. Moreover, we show that the corresponding non-existence result holds for 4-(v, k, 1) designs, except possibly when the group is 1-D affine. Our approach involves a consideration of the finite 2-homogeneous affine permutation groups.     

The existence of (2 × c, λ) grid-block designs with {c\in \{3, 4, 5\}} and λ ≥ 1

Let X be a v-set and ${\mathcal{B}}$ a collection of r × c arrays with elements in X. Two elements of X are collinear if they are on the same grid line (row or column). A pair ${(X, \mathcal{B})}$ is called an (r × c, λ) grid-block design if every two distinct elements in X are collinear exactly λ times in the arrays of ${\mathcal{B}}$ . This design has absorbed much attention due to its use in DNA library screening. In this paper, we prove that the necessary conditions for the existence of (2 × c, λ) grid-block designs of order v with ${c\in \{3, 4, 5\}}$ and any integer λ ≥ 1 are also sufficient.     

Nonisomorphic Maximum Packing and Minimum Covering of K v with 8-Cycles

The maximum packing C ₈-max PD(v) and minimum covering C ₈-minCD(v) of K _v with 8-cycles are studied, all structures with the nonisomorphic leave (excess) are presented. In Li et al. (Graphs Combin 25:735–752, 2009), C ₈-max PD(v) and C ₈-minCD(v) have been determined for odd v. In this paper, we introduce the enumeration of nonisomorphic ${(v,\frac{v}{2}+s)}$ -graphs (s = 4, 6), give complete solution of the maximum packing and minimum covering designs of K _v with 8-cycles for any even v with all possible leaves (excesses).