Cycle Extensions in BIBD Block‐Intersection Graphs

A cycle C in a graph G is extendable if there is some other cycle in G that contains each vertex of C plus one additional vertex. A graph is cycle extendable if every non‐Hamilton cycle in the graph is extendable. A balanced incomplete block design, BIBD, consists of a set V of v elements and a block set of k‐subsets of V such that each 2‐subset of V occurs in exactly λ of the blocks of . The block‐intersection graph of a design is the graph having as its vertex set and such that two vertices of are adjacent if and only if their corresponding blocks have nonempty intersection. In this paper, we prove that the block‐intersection graph of any BIBD is cycle extendable. Furthermore, we present a polynomial time algorithm for constructing cycles of all possible lengths in a block‐intersection graph.     

Perfect 1‐Factorizations of a Family of Cayley Graphs

A 1‐factorization of a graph G is a decomposition of G into edge‐disjoint 1‐factors (perfect matchings), and a perfect 1‐factorization is a 1‐factorization in which the union of any two of the 1‐factors is a Hamilton cycle. We consider the problem of the existence of perfect 1‐factorizations of even order 4‐regular Cayley graphs, with a particular interest in circulant graphs. In this paper, we study a new family of graphs, denoted , which are Cayley graphs if and only if k is even or . By solving the perfect 1‐factorization problem for a large class of graphs, we obtain a new class of 4‐regular bipartite circulant graphs that do not have a perfect 1‐factorization, answering a problem posed in 7 . With further study of graphs, we prove the nonexistence of P1Fs in a class of 4‐regular non‐bipartite circulant graphs, which is further support for a conjecture made in 7 .     

New Infinite Families of 2‐Edge‐Balanced Graphs

A graph G of order n is called t‐edge‐balanced if G satisfies the property that there exists a positive λ for which every graph of order n and size t is contained in exactly λ distinct subgraphs of isomorphic to G. We call λ the index of G. In this article, we obtain new infinite families of 2‐edge‐balanced graphs.     

Set Systems with L‐Intersections and k‐Wise L‐Intersecting Families

In this paper, by employing linear algebra methods we obtain the following main results:

• (i) Let and be two disjoint subsets of such that Suppose that is a family of subsets of such that for every pair and for every i. Then Furthermore, we extend this theorem to k‐wise L‐intersecting and obtain the corresponding result on two cross L‐intersecting families. These results show that Snevily's conjectures proposed by Snevily (2003) are true under some restricted conditions. This result also gets an improvement of a theorem of Liu and Hwang (2013).
• (ii) Let p be a prime and let and be two subsets of such that or and Suppose that is a family of subsets of [n] such that (1) for every pair (2) for every i. Then This result improves the existing upper bound substantially.

     

New i‐Perfect Cycle Decompositions via Vertex Colorings of Graphs

Generalizing a result by Buratti et al.[M. Buratti, F. Rania, and F. Zuanni, Some constructions for cyclic perfect cycle systems, Discrete Math 299 (2005), 33–48], we present a construction for i‐perfect k‐cycle decompositions of the complete m‐partite graph with parts of size k. These decompositions are sharply vertex‐transitive under the additive group of with R a suitable ring of order m. The construction works whenever a suitable i‐perfect map exists. We show that for determining the set of all triples for which such a map exists, it is crucial to calculate the chromatic numbers of some auxiliary graphs. We completely determine this set except for one special case where is the product of two distinct primes, is even, and . This result allows us to obtain a plethora of new i‐perfect k‐cycle decompositions of the complete graph of order (mod 2k) with k odd. In particular, if k is a prime, such a decomposition exists for any possible i provided that .     

Decomposition of Complete Graphs into Isomorphic Complete Bipartite Graphs

A decomposition of a complete graph into disjoint copies of a complete bipartite graph is called a ‐design of order n. The existence problem of ‐designs has been completely solved for the graphs for , for , K_{2, 3} and K_{3, 3}. In this paper, I prove that for all , if there exists a ‐design of order N, then there exists a ‐design of order n for all (mod ) and . Giving necessary direct constructions, I provide an almost complete solution for the existence problem for complete bipartite graphs with fewer than 18 edges, leaving five orders in total unsolved.     

On Flag‐Transitive Symmetric Designs of Affine Type

It is shown that, if is a nontrivial 2‐ symmetric design, with , admitting a flag‐transitive automorphism group G of affine type, then , p an odd prime, and G is a point‐primitive, block‐primitive subgroup of . Moreover, acts flag‐transitively, point‐primitively on , and is isomorphic to the development of a difference set whose parameters and structure are also provided.     

Classification of Graeco‐Latin Cubes

A q‐ary code of length n, size M, and minimum distance d is called an code. An code with is said to be maximum distance separable (MDS). Here one‐error‐correcting () MDS codes are classified for small alphabets. In particular, it is shown that there are unique (5, 5³, 3)₅ and (5, 7³, 3)₇ codes and equivalence classes of (5, 8³, 3)₈ codes. The codes are equivalent to certain pairs of mutually orthogonal Latin cubes of order q, called Graeco‐Latin cubes.     

Three‐Phase Barker Arrays

A 3‐phase Barker array is a matrix of third roots of unity for which all out‐of‐phase aperiodic autocorrelations have magnitude 0 or 1. The only known truly two‐dimensional 3‐phase Barker arrays have size 2 × 2 or 3 × 3. We use a mixture of combinatorial arguments and algebraic number theory to establish severe restrictions on the size of a 3‐phase Barker array when at least one of its dimensions is divisible by 3. In particular, there exists a double‐exponentially growing arithmetic function T such that no 3‐phase Barker array of size with exists for all . For example, , , and . When both dimensions are divisible by 3, the existence problem is settled completely: if a 3‐phase Barker array of size exists, then .     

Embedding Partial k‐Star Designs

A k‐star is the complete bipartite graph . Let G and H be graphs, and let be a partial H‐decomposition of G. A partial H‐decomposition, , of another graph is called an embedding of provided that and G is a subgraph of . We find an embedding of a partial k‐star decomposition of into a k‐star decomposition of , where s is at most if k is odd, and if k is even.     

Flag‐Transitive Point‐Primitive Symmetric (ν,κ,λ) Designs With λ at Most 100

Let be a symmetric (ν,κ,λ) design with λ ≤ 100. If G is a flag‐transitive and point‐primitive automorphism group of , then G must be an affine or almost simple group.     

Large Cross‐Free Sets in Steiner Triple Systems

A cross‐free set of size m in a Steiner triple system is three pairwise disjoint m‐element subsets such that no intersects all the three ‐s. We conjecture that for every admissible n there is an STS(n) with a cross‐free set of size which if true, is best possible. We prove this conjecture for the case , constructing an STS containing a cross‐free set of size 6k. We note that some of the 3‐bichromatic STSs, constructed by Colbourn, Dinitz, and Rosa, have cross‐free sets of size close to 6k (but cannot have size exactly 6k). The constructed STS shows that equality is possible for in the following result: in every 3‐coloring of the blocks of any Steiner triple system STS(n) there is a monochromatic connected component of size at least (we conjecture that equality holds for every admissible n). The analog problem can be asked for r‐colorings as well, if and is a prime power, we show that the answer is the same as in case of complete graphs: in every r‐coloring of the blocks of any STS(n), there is a monochromatic connected component with at least points, and this is sharp for infinitely many n.     

Finiteness Results in Triangle‐Free Quasi‐Symmetric Designs

Triangle‐free quasi‐symmetric 2‐ designs with intersection numbers ; and are investigated. Possibility of triangle‐free quasi‐symmetric designs with or is ruled out. It is also shown that, for a fixed x and a fixed ratio , there are only finitely many triangle‐free quasi‐symmetric designs. © 2012 Wiley Periodicals, Inc. J Combin Designs 00: 1‐6, 2012     

Block‐Transitive and Point‐Primitive 2‐ Designs with Sporadic Socle

The purpose of this paper is to classify all pairs , where is a nontrivial 2‐ design, and acts transitively on the set of blocks of and primitively on the set of points of with sporadic socle. We prove that there exists only one such pair : is the unique 2‐(176,8,2) design and , the Higman–Sims simple group.     

A Generalization of the Hamilton–Waterloo Problem on Complete Equipartite Graphs

The Hamilton–Waterloo problem asks for which s and r the complete graph can be decomposed into s copies of a given 2‐factor F₁ and r copies of a given 2‐factor F₂ (and one copy of a 1‐factor if n is even). In this paper, we generalize the problem to complete equipartite graphs and show that can be decomposed into s copies of a 2‐factor consisting of cycles of length xzm; and r copies of a 2‐factor consisting of cycles of length yzm, whenever m is odd, , , and . We also give some more general constructions where the cycles in a given two factor may have different lengths. We use these constructions to find solutions to the Hamilton–Waterloo problem for complete graphs.     

Cycle Frames of Complete Multipartite Multigraphs ‐ III

For two graphs G and H their wreath product has vertex set in which two vertices and are adjacent whenever or and . Clearly, , where is an independent set on n vertices, is isomorphic to the complete m‐partite graph in which each partite set has exactly n vertices. A 2‐regular subgraph of the complete multipartite graph containing vertices of all but one partite set is called partial 2‐factor. For an integer λ, denotes a graph G with uniform edge multiplicity λ. Let J be a set of integers. If can be partitioned into edge‐disjoint partial 2‐factors consisting cycles of lengths from J, then we say that has a ‐cycle frame. In this paper, we show that for and , there exists a ‐cycle frame of if and only if and . In fact our results completely solve the existence of a ‐cycle frame of .     

4‐*GDD(6n)s and Related Optimal Quaternary Constant‐Weight Codes

Constant‐weight codes (CWCs) have played an important role in coding theory. To construct CWCs, a K‐GDD (where GDD is group divisible design) with the “star” property, denoted by K‐*GDD, was introduced, in which any two intersecting blocks intersect in at most two common groups. In this paper, we consider the existence of 4‐*GDDs. Previously, the necessary conditions for existence were shown to be sufficient for , and also sufficient for with prime powers and . We continue to investigate the existence of 4‐*GDD(6ⁿ)s and show that the necessary condition for the existence of a 4‐*GDD(6ⁿ), namely, , is also sufficient. The known results on the existence of optimal quaternary (n, 5, 4) CWCs are also extended.     

Turyn‐Type Sequences: Classification,Enumeration, and Construction

Turyn‐type sequences, , are quadruples of ‐sequences , with lengths , respectively, where the sum of the nonperiodic autocorrelation functions of and twice that of is a δ‐function (i.e., vanishes everywhere except at 0). Turyn‐type sequences are known to exist for all even n not larger than 36. We introduce a definition of equivalence to construct a canonical form for in general. By using this canonical form, we enumerate the equivalence classes of for . We also construct the first example of Turyn‐type sequences .     

On the Choice Number of Packings

In this note, we show that for positive integers s and k, there is a function such that every t‐ packing with at least edges, , has choice number greater than s. Consequently, for integers s, k, t, and λ there is a such that every t‐ design with has choice number greater than s. © 2012 Wiley Periodicals, Inc. J. Combin. Designs 20: 504‐507, 2012