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     

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 .     

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.     

Ovoids of generalized quadrangles of order and Delsarte cocliques in related strongly regular graphs

We investigate strongly regular graphs for which Hoffman's ratio bound and Cvetcović's inertia bound are equal. This means that , where v is the number of vertices, k is the regularity, is the smallest eigenvalue, and is the multiplicity of . We show that Delsarte cocliques do not exist for all Taylor's 2‐graphs and for point graphs of generalized quadrangles of order for infinitely many q. For cases where equality may hold, we show that for nearly all parameter sets, there are at most two Delsarte cocliques.     

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 .     

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.     

Twofold triple systems with cyclic 2‐intersecting Gray codes

Given a combinatorial design with block set , the block‐intersection graph (BIG) of is the graph that has as its vertex set, where two vertices and are adjacent if and only if . The i‐block‐intersection graph (i‐BIG) of is the graph that has as its vertex set, where two vertices and are adjacent if and only if . In this paper, several constructions are obtained that start with twofold triple systems (TTSs) with Hamiltonian 2‐BIGs and result in larger TTSs that also have Hamiltonian 2‐BIGs. These constructions collectively enable us to determine the complete spectrum of TTSs with Hamiltonian 2‐BIGs (equivalently TTSs with cyclic 2‐intersecting Gray codes) as well as the complete spectrum for TTSs with 2‐BIGs that have Hamilton paths (i.e. for TTSs with 2‐intersecting Gray codes). In order to prove these spectrum results, we sometimes require ingredient TTSs that have large partial parallel classes; we prove lower bounds on the sizes of partial parallel classes in arbitrary TTSs, and then construct larger TTSs with both cyclic 2‐intersecting Gray codes and parallel classes.     

Perfect Matchings of Regular Bipartite Graphs

Let G be a regular bipartite graph and . We show that there exist perfect matchings of G containing both, an odd and an even number of edges from X if and only if the signed graph , that is a graph G with exactly the edges from X being negative, is not equivalent to . In fact, we prove that for a given signed regular bipartite graph with minimum signature, it is possible to find perfect matchings that contain exactly no negative edges or an arbitrary one preselected negative edge. Moreover, if the underlying graph is cubic, there exists a perfect matching with exactly two preselected negative edges. As an application of our results we show that each signed regular bipartite graph that contains an unbalanced circuit has a 2‐cycle‐cover such that each cycle contains an odd number of negative edges.     

Partitioning the edge set of a hypergraph into almost regular cycles

A cycle of length t in a hypergraph is an alternating sequence of distinct vertices and distinct edges so that (with ). Let be the λ‐fold n‐vertex complete h‐graph. Let be a hypergraph all of whose edges are of size at least h, and . In order to partition the edge set of into cycles of specified lengths , an obvious necessary condition is that . We show that this condition is sufficient in the following cases.

• (R1) .
• (R2) , .
• (R3) , , .

In (R2), we guarantee that each cycle is almost regular. In (R3), we also solve the case where a “small” subset L of edges of is removed.     

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.     

On the Existence of Friendship Hypergraphs

A 3‐uniform friendship hypergraph is a 3‐uniform hypergraph in which, for all triples of vertices x, y, z there exists a unique vertex w, such that , and are edges in the hypergraph. Sós showed that such 3‐uniform friendship hypergraphs on n vertices exist with a so‐called universal friend if and only if a Steiner triple system, exists. Hartke and Vandenbussche used integer programming to search for 3‐uniform friendship hypergraphs without a universal friend and found one on 8, three nonisomorphic on 16 and one on 32 vertices. So far, these five hypergraphs are the only known 3‐uniform friendship hypergraphs. In this paper we construct an infinite family of 3‐uniform friendship hypergraphs on 2^k vertices and edges. We also construct 3‐uniform friendship hypergraphs on 20 and 28 vertices using a computer. Furthermore, we define r‐uniform friendship hypergraphs and state that the existence of those with a universal friend is dependent on the existence of a Steiner system, . As a result hereof, we know infinitely many 4‐uniform friendship hypergraphs with a universal friend. Finally we show how to construct a 4‐uniform friendship hypergraph on 9 vertices and with no universal friend.     

Doyen–Wilson Results for Odd Length Cycle Systems

For each odd , we completely solve the problem of when an m‐cycle system of order u can be embedded in an m‐cycle system of order v, barring a finite number of possible exceptions. In cases where u is large compared to m, where m is a prime power, or where , the problem is completely resolved. In other cases, the only possible exceptions occur when is small compared to m. This result is proved as a consequence of a more general result that gives necessary and sufficient conditions for the existence of an m‐cycle decomposition of a complete graph of order v with a hole of size u in the case where and both hold.     

Some Results on 1‐Rotational Hamiltonian Cycle Systems

A Hamiltonian cycle system of (briefly, a HCS(v)) is 1‐rotational under a (necessarily binary) group G if it admits G as an automorphism group acting sharply transitively on all but one vertex. We first prove that for any there exists a 3‐perfect 1‐rotational HCS. This allows to get the existence of another infinite class of 3‐perfect (but not Hamiltonian) cycle decompositions of the complete graph. Then we prove that the full automorphism group of a 1‐rotational HCS under G is G itself unless the HCS is the 2‐transitive one. This allows us to give a partial answer to the problem of determining which abstract groups are the full automorphism group of a HCS. Finally, we revisit and simplify by means of a careful group theoretic discussion a formula by Bailey, Ollis, and Preece on the number of inequivalent 1‐rotational HCSs under G. This leads us to a formula counting all 1‐rotational HCSs up to isomorphism. Though this formula heavily depends on some parameters that are hard to compute, it allows us to say that, for any , there are at least nonisomorphic 1‐rotational (and hence symmetric) HCS().     

Optimal Groomings with Grooming Ratios Six and Seven

Grooming uniform all‐to‐all traffic in optical (SONET) rings with grooming ratio C requires the determination of a decomposition of the complete graph into subgraphs each having at most C edges. The drop cost of such a grooming is the total number of vertices of nonzero degree in these subgraphs, and the grooming is optimal when the drop cost is minimum. The determination of optimal C‐groomings has been considered for , and completely solved for . For , it has been shown that the lower bound for the drop cost of an optimal C‐grooming can be attained for almost all orders with 5 exceptions and 308 possible exceptions. For , there are infinitely many unsettled orders; especially the case is far from complete. In this paper, we show that the lower bound for the drop cost of a 6‐grooming can be attained for almost all orders by reducing the 308 possible exceptions to 3, and that the lower bound for the drop cost of a 7‐grooming can be attained for almost all orders with seven exceptions and 16 possible exceptions. Moreover, for the unsettled orders, we give upper bounds for the minimum drop costs.     

The Asymptotic Existence of Resolvable Group Divisible Designs

A group divisible design (GDD) is a triple which satisfies the following properties: (1) is a partition of X into subsets called groups; (2) is a collection of subsets of X, called blocks, such that a group and a block contain at most one element in common; and (3) every pair of elements from distinct groups occurs in a constant number λ blocks. This parameter λ is usually called the index. A k‐GDD of type is a GDD with block size k, index , and u groups of size g. A GDD is resolvable if the blocks can be partitioned into classes such that each point occurs in precisely one block of each class. We denote such a design as an RGDD. For fixed integers and , we show that the necessary conditions for the existence of a k‐RGDD of type are sufficient for all . As a corollary of this result and the existence of large resolvable graph decompositions, we establish the asymptotic existence of resolvable graph GDDs, G‐RGDDs, whenever the necessary conditions for the existence of ‐RGDs are met. We also show that, with a few easy modifications, the techniques extend to general index. © 2012 Wiley Periodicals, Inc. J. Combin. Designs 21: 112–126, 2013     

Dihedral Hamiltonian Cycle Systems of the Cocktail Party Graph

The existence problem for a Hamiltonian cycle decomposition of (the so called cocktail party graph) with a dihedral automorphism group acting sharply transitively on the vertices is completely solved. Such Hamiltonian cycle decompositions exist for all even n while, for n odd, they exist if and only if the following conditions hold: (i) n is not a prime power; (ii) there is a suitable ? such that (mod 2^?) for all prime factors p of n and the number of the prime factors (counted with their respective multiplicities) such that (mod ) is even. Thus in particular one has a dihedral Hamiltonian cycle decomposition of the cocktail party graph on 8k vertices for all k, while it is known that no such cyclic Hamiltonian cycle decomposition exists. Finally, this paper touches on a recently introduced symmetry requirement by proving that there exists a dihedral and symmetric Hamiltonian cycle system of if and only if (mod 4).     

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.     

Group Divisible Covering Designs with Block Size 4: A Type of Covering Array with Row Limit

A k‐GDCD, group divisible covering design, of type is a triple , where V is a set of gu elements, is a partition of V into u sets of size g, called groups, and is a collection of k‐subsets of V, called blocks, such that every pair of elements in V is either contained in a unique group or there is at least one block containing it, but not both. This family of combinatorial objects is equivalent to a special case of the graph covering problem and a generalization of covering arrays, which we call CARLs. In this paper, we show that there exists an integer such that for any positive integers g and , there exists a 4‐GDCD of type which in the worst case exceeds the Schönheim lower bound by δ blocks, except maybe when (1) and , or (2) , , and or . To show this, we develop constructions of 4‐GDCDs, which depend on two types of ingredients: essential, which are used multiple times, and auxiliary, which are used only once in the construction. If the essential ingredients meet the lower bound, the products of the construction differ from the lower bound by as many blocks as the optimal size of the auxiliary ingredient differs from the lower bound.     

The Existence and Construction of (K5∖e)‐Designs of Orders 27, 135, 162, and 216

The problem of the existence of a decomposition of the complete graph into disjoint copies of has been solved for all admissible orders n, except for 27, 36, 54, 64, 72, 81, 90, 135, 144, 162, 216, and 234. In this paper, I eliminate 4 of these 12 unresolved orders. Let Γ be a ‐design. I show that divides 2^k3 for some and that . I construct ‐designs by prescribing as an automorphism group, and show that up to isomorphism there are exactly 24 ‐designs with as an automorphism group. Moreover, I show that the full automorphism group of each of these designs is indeed . Finally, the existence of ‐designs of orders 135, 162, and 216 follows immediately by the recursive constructions given by G. Ge and A. C. H. Ling, SIAM J Discrete Math 21(4) (2007), 851–864.     

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.