On the existence of resolvable K4 − e designs

In this article, we settle a problem which originated in 4 regarding the existence of resolvable (K₄ ? e)‐design. We solve the problem with two possible exceptions. © 2007 Wiley Periodicals, Inc. J Combin Designs 15: 502–510, 2007     

Alternating groups and flag‐transitive 2‐(v,k, 4) symmetric designs

In this article, we study the classification of flag‐transitive, point‐primitive 2‐ (v, k, 4) symmetric designs. We prove that if the socle of the automorphism group G of a flag‐transitive, point‐primitive nontrivial 2‐ (v, k, 4) symmetric design ?? is an alternating group A_n for n≥5, then (v, k) = (15, 8) and ?? is one of the following: (i) The points of ?? are those of the projective space PG(3, 2) and the blocks are the complements of the planes of PG(3, 2), G = A₇ or A₈, and the stabilizer G_x of a point x of ?? is L₃(2) or AGL₃(2), respectively. (ii) The points of ?? are the edges of the complete graph K₆ and the blocks are the complete bipartite subgraphs K_{2, 4} of K₆, G = A₆ or S₆, and G_x = S₄ or S₄ × Z₂, respectively. © 2011 Wiley Periodicals, Inc. J Combin Designs 19:475‐483, 2011     

Minimum embedding of Steiner triple systems into -designs I

A (K₄-e)-design on v+w points embeds a Steiner triple system (STS) if there is a subset of v points on which the graphs of the design induce the blocks of a STS. It is established that wv/3, and that when equality is met that such a minimum embedding of an STS(v) exists, except when v=15.     

Resolvable even‐cycle systems with a 1‐rotational automorphism

In this article, necessary and sufficient conditions for the existence of a 1‐rotationally resolvable even‐cycle system of λK_v are given, which are eventually for the existence of a resolvable even‐cycle system of λK_v. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 394–407, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10058     

Some results on λ‐designs with two block sizes

A λ‐design is a family ?? = {B₁, B₂, …, B_v} of subsets of X = {1, 2, …, v} such that |B_i∩B_j| = λ for all i≠jand not all B_i are of the same size. The only known example of λ‐designs (called type‐1 designs) are those obtained from symmetric designs by a certain complementation procedure. Ryser [J Algebra 10 (1968), 246–261] and Woodall [Proc London Math Soc 20 (1970), 669–687] independently conjectured that all λ‐designs are type‐1. Let g = gcd(r ? 1, r^* ? 1), where rand r^* are the two replication numbers. Ionin and Shrikhande [J Combin Comput 22 (1996), 135–142; J Combin Theory Ser A 74 (1996), 100–114] showed that λ‐designs with g = 1, 2, 3, 4 are type‐1 and that the Ryser–Woodall conjecture is true for λ‐designs on p + 1, 2p + 1, 3p + 1, 4p + 1 points, where pis a prime. Hein and Ionin [Codes and Designs—Proceedings of Conference honoring Prof. D. K. Ray‐Chaudhuri on the occasion of his 65th birthday, Ohio State University Mathematical Research Institute Publications, 10, Walter de Gruyter, Berlin, 2002, pp. 145–156] proved corresponding results for g = 5 and Fiala [Codes and Designs—Proceedings of Conference honoring Prof. D. K. Ray‐Chaudhuri on the occasion of his 65th birthday, Ohio State University Mathematical Research Institute Publications, 10, Walter de Gruyter, Berlin, 2002, pp. 109–124; Ars Combin 68 (2003), 17–32; Ars Combin, to appear] for g = 6, 7, and 8. In this article, we consider λ designs with exactly two block sizes. We show that in this case, the conjecture is true for g = 9, 11, 12, 13, 15, 16, 17, 19, 20, 21, and for g = 10, 14, 18, 22 with v≠4λ ? 1. We also give two results on such λ‐designs on v = 9p + 1 and 12p + 1 points, where pis a prime. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:95‐110, 2011     

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.     

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.     

A small generating set for the 3‐BD closed set of block sizes ≥ 6

Let v, k be positive integers and k ≥ 3, then K_k = : {v: v ≥ k} is a 3‐BD closed set. Two finite generating sets of 3‐BD closed sets K₄ and K₅ are obtained by H. Hanani [5] and Qiurong Wu [12] respectively. In this article we show that if v ≥ 6, then v ∈ B₃(K,1), where K = {6,7,…,41,45,46,47,51,52,53,83,84}\{22,26}; that is, we show that K is a generating set for K₆. Finally we show that v ∈ B₃(6,20) for all v ∈ K\{35,39,40,45}. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 128–136, 2008     

Some rigid Steiner 5‐designs

Hitherto, all known non‐trivial Steiner systems S(5, k, v) have, as a group of automorphisms, either PSL(2, v−1) or PGL(2, (v−2)/2) × C₂. In this article, systems S(5, 6, 72), S(5, 6, 84) and S(5, 6, 108) are constructed that have only the trivial automorphism group. © 2010 Wiley Periodicals, Inc. J Combin Designs 18:392–400, 2010     

On the 3BD‐closed set B3({4,5,6})

Let B₃(K) = {v:? an S(3,K,v)}. For K = {4} or {4,6}, B₃(K) has been determined by Hanani, and for K = {4, 5} by a previous paper of the author. In this paper, we investigate the case of K = {4,5,6}. It is easy to see that if v ∈ B₃ ({4, 5, 6}), then v ≡ 0, 1, 2 (mod 4). It is known that B₃{4, 6}) = {v > 0: v ≡ 0 (mod 2)} ? B₃({4,5,6}) by Hanani and that B₃({4, 5}) = {v > 0: v ≡ 1, 2, 4, 5, 8, 10 (mod 12) and v ≠ 13} ? B₃({4, 5, 6}). We shall focus on the case of v ≡ 9 (mod 12). It is proved that B₃({4,5,6}) = {v > 0: v ≡ 0, 1, 2 (mod 4) and v ≠ 9, 13}. © 2003 Wiley Periodicals, Inc.     

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).     

Resolvable packings of Kv with K2 × Kc's

The study of resolvable packings of K_v with K_r × K_c's is motivated by the use of DNA library screening. We call such a packing a (v, K_r × K_c, 1)‐RP. As usual, a (v, K_r × K_c, 1)‐RP with the largest possible number of parallel classes (or, equivalently, the largest possible number of blocks) is called optimal. The resolvability implies v ≡ 0 (mod rc). Let ρ be the number of parallel classes of a (v, K_r × K_c, 1)‐RP. Then we have ρ ≤ ?(v‐1)/(r + c ? 2)?. In this article, we present a number of constructive methods to obtain optimal (v, K₂ × K_c, 1)‐RPs meeting the aforementioned bound and establish some existence results. In particular, we show that an optimal (v, K₂ × K₃, 1)‐RP meeting the bound exists if and only if v ≡ 0 (mod 6). © 2008 Wiley Periodicals, Inc. J Combin Designs 17: 177–189, 2009     

α‐Resolvable group divisible designs with block size three

A group divisible design GD(k,λ,t;tu) is α‐resolvable if its blocks can be partitioned into classes such that each point of the design occurs in precisely α blocks in each class. The necessary conditions for the existence of such a design are λt(u ? 1) = r(k ? 1), bk = rtu, k|αtu and α|r. It is shown in this paper that these conditions are also sufficient when k = 3, with some definite exceptions. © 2004 Wiley Periodicals, Inc.     

Super‐simple holey Steiner pentagon systems and related designs

A Steiner pentagon system of order v (SPS(v)) is said to be super‐simple if its underlying (v, 5, 2)‐BIBD is super‐simple; that is, any two blocks of the BIBD intersect in at most two points. It is well known that the existence of a holey Steiner pentagon system (HSPS) of type T implies the existence of a (5, 2)‐GDD of type T. We shall call an HSPS of type T super‐simple if its underlying (5, 2)‐GDD of type T is super‐simple; that is, any two blocks of the GDD intersect in at most two points. The existence of HSPSs of uniform type hⁿ has previously been investigated by the authors and others. In this article, we focus our attention on the existence of super‐simple HSPSs of uniform type hⁿ. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 301–328, 2008     

Doubly transitive 2‐factorizations

Let be a 2‐factorization of the complete graph K_v admitting an automorphism group G acting doubly transitively on the set of vertices. The vertex‐set V(K_v) can then be identified with the point‐set of AG(n, p) and each 2‐factor of is the union of p‐cycles which are obtained from a parallel class of lines of AG(n, p) in a suitable manner, the group G being a subgroup of A G L(n, p) in this case. The proof relies on the classification of 2‐(v, k, 1) designs admitting a doubly transitive automorphism group. The same conclusion holds even if G is only assumed to act doubly homogeneously. © 2006 Wiley Periodicals, Inc. J Combin Designs     

Correction to: “Exponential bounds on the number of designs with affine parameters”

It is well known that the number of designs with the parameters of a classical design having as blocks the hyperplanes in PG(n, q) or AG(n, q), n?3, grows exponentially. This result was extended recently [5] to designs having the same parameters as a projective geometry design whose blocks are the d‐subspaces of PG(n, q), for any 2?d?n ? 1. In this paper, exponential lower bounds are proved on the number of non‐isomorphic designs having the same parameters as an affine geometry design whose blocks are the d‐subspaces of AG(n, q), for any 2≤d≤n ? 1. Exponential bounds are also proved for the number of resolvable designs with these parameters. © 2011 Wiley Periodicals, Inc. J Combin Designs 19:156‐166, 2011     

Coloring 4‐cycle systems

An m‐cycle system of order n is a partition of the edges of the complete graph K_n into m‐cycles. We investigate k‐colorings of 4‐cycle systems in which no 4‐cycle is monochromatic. For any k ≥ 3, we construct a k‐chromatic 4‐cycle system. We also show that for any k ge; 2, there exists an integer w_k such that for all admissible n ≥ w_k, there is a k‐chromatic 4‐cycle system of order n. © 2005 Wiley Periodicals, Inc. J Combin Designs     

Nowhere‐zero 3‐flows in locally connected graphs

Let G be a graph. For each vertex v ∈V(G), N_v denotes the subgraph induces by the vertices adjacent to v in G. The graph G is locally k‐edge‐connected if for each vertex v ∈V(G), N_v is k‐edge‐connected. In this paper we study the existence of nowhere‐zero 3‐flows in locally k‐edge‐connected graphs. In particular, we show that every 2‐edge‐connected, locally 3‐edge‐connected graph admits a nowhere‐zero 3‐flow. This result is best possible in the sense that there exists an infinite family of 2‐edge‐connected, locally 2‐edge‐connected graphs each of which does not have a 3‐NZF. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 211–219, 2003     

Cyclic k‐cycle systems of order 2kn + k: A solution of the last open cases

We exhibit cyclic (K_v, C_k)‐designs with v > k, v ≡ k (mod 2k), for k an odd prime power but not a prime, and for k = 15. Such values were the only ones not to be analyzed yet, under the hypothesis v ≡ k (mod 2k). Our construction avails of Rosa sequences and approximates the Hamiltonian case (v = k), which is known to admit no cyclic design with the same values of k. As a particular consequence, we settle the existence question for cyclic (K_v, C_k)‐designs with k a prime power. © 2004 Wiley Periodicals, Inc. J Combin Designs 12: 299–310, 2004.     

The structure of saturated critical blocks

A 2‐connected graph G is a critical block if G ? v is not 2‐connected for every vertex v ∈ V(G). A critical block G is a saturated critical block if G + e is not a critical block for any new edge e. The structure of all saturated critical blocks and a procedure for constructing every saturated critical block are determined. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 223–237, 2003